2012 OnlineAllocationofDisplayAdswit

Subject Headings:

Notes

Display ads on the Internet are often sold in bundles of thousands or millions of impressions over a particular time period, typically weeks or months. Ad serving systems that assign ads to pages on behalf of publishers must satisfy these contracts, but at the same time try to maximize overall quality of placement. This is usually modeled in the literature as an online allocation problem, where contracts are represented by overall delivery constraints over a finite time horizon. However this model misses an important aspect of ad delivery: time homogeneity. Advertisers who buy these packages expect their ad to be shown smoothly throughout the purchased time period, in order to reach a wider audience, to have a sustained impact, and to support the ads they are running on other media (e.g., television). In this paper we formalize this problem using several nested packing constraints, and develop a tight (1-1 / e) - competitive online algorithm for this problem. Our algorithms and analysis require novel techniques as they involve online computation of multiple dual variables per ad. We then show the effectiveness of our algorithms through exhaustive simulation studies on real data sets.

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 OnlineAllocationofDisplayAdswit	Anand Bhalgat Jon Feldman Vahab Mirrokni			Online Allocation of Display Ads with Smooth Delivery				10.1145/2339530.2339720		2012