document: A combinatorial allocation mechanism with penalties for banner advertising 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 ` 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 a monetary payment 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 heuristics and discuss theoretical techniques to measure 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 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 might 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 structural approximation result , a newly defined framework for evaluating heuristics ( 10 ) . We thereby prove that this algorithm has a better performance guarantee than the simple greedy algorithm .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O