Data Portal @ linkeddatafragments.org

Matches in ScholarlyData for { <https://w3id.org/scholarlydata/inproceedings/www2008/paper/729> ?p ?o. }

• 729 creator hamid-nazerzadeh.
• 729 creator nicole-immorlica.
• 729 creator uriel-feige.
• 729 creator vahab-mirrokni.
• 729 type InProceedings.
• 729 label "A combinatorial allocation mechanism with penalties for banner advertising".
• 729 sameAs 729.
• 729 abstract "Most current banner advertising is sold through negotiation thereby incurring large transaction costs and possibly suboptimal allocations. We propose a new automated system for selling banner advertising. In this system, each advertiser specifies a collection of host webpages which are relevant to his product, a desired total quantity of impressions on these pages, and a maximum per-impression price. The system selects a subset of advertisers as {\em winners} and maps each winner to a set of impressions on pages within his desired collection. The distinguishing feature of our system as opposed to current combinatorial allocation mechanisms is that, mimicking the current negotiation system, we guarantee that winners receive at least as many advertising opportunities as they requested or else receive ample compensation in the form of monetary paid by the host. Such guarantees are essential in markets like banner advertising where a major goal of the advertising campaign is developing brand recognition. As we show, the problem of selecting a feasible subset of advertisers with maximum total value is inapproximable. We thus present two greedy heuristic and discuss theoretical techniques to measures their performances. Our first algorithm iteratively selects advertisers and corresponding sets of impressions which contribute maximum marginal per-impression profit to the current solution. We prove a {\em bi-criteria approximation} for this algorithm, showing that it generates approximately as much value as the optimum algorithm on a slightly harder problem. However, this algorithm may perform poorly on instances in which the value of the optimum solution is quite large, a clearly undesirable failure mode. Hence, we present an adaptive greedy algorithm which again iteratively selects advertisers with maximum marginal per-impression profit, but additionally reassigns impressions at each iteration. For this algorithm, we prove a {\em functional approximation} result, a newly defined framework for evaluating heuristics~\cite{FIMN08}. We thereby prove that this algorithm has a better performance guarantee than the simple greedy algorithm when the optimum value is large.".
• 729 hasAuthorList authorList.
• 729 hasTopic World_Wide_Web.
• 729 isPartOf proceedings.
• 729 keyword "Approximation Algorithm".
• 729 keyword "Combinatorial Auction".
• 729 keyword "Functional Approximation".
• 729 keyword "Internet Advertising".
• 729 keyword "Supply Guarantee".
• 729 title "A combinatorial allocation mechanism with penalties for banner advertising".