Online allocation of display advertisements subject to advanced sales contracts

ABSTRACT

In this paper we propose a utility model that accounts for both sales and branding advertisers. We first study the computational complexity of optimization problems related to both online and offline allocation of display advertisements. Next, we focus on a particular instance of the online allocation problem, and design a simple online algorithm with provable approximation guarantees. Our algorithm is near optimal as is shown by a matching lower bound. Finally, we report on experiments to establish actual case behavior on some real datasets, with encouraging results.

REFERENCES

• 1: Arash Asadpour , Amin Saberi, An approximation algorithm for max-min fair allocation of indivisible goods, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250808]
• 2: Nikhil Bansal , Maxim Sviridenko, The Santa Claus problem, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132522]
• 3: Gruia Calinescu , Amit Chakrabarti , Howard J. Karloff , Yuval Rabani, Improved Approximation Algorithms for Resource Allocation, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.401-414, May 27-29, 2002
• 4: Leah Epstein , Asaf Levin, Improved Randomized Results for That Interval Selection Problem, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_32]
• 5: Ureil Feige , Nicole Immorlica , Vahab Mirrokni , Hamid Nazerzadeh, A combinatorial allocation mechanism with penalties for banner advertising, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367521]
• 6: S. Fung, C. Poon, and F. Zheng. Improved randomized online scheduling of unit length intervals and jobs. In WAOA, 2008.
• 7: J. James D. Dana. Advance-purchase discounts and price discrimination in competitive markets. Journal of Political Economy, 106(21):395--422, 1998.
• 8: R. Lewis and D. Reiley. Retail advertising works! measuring the effects of advertising on sales via a controlled experiment on yahoo! Technical report, Yahoo! Research, 2008.
• 9: COIN-OR Foundation: http://www.coin-or.org.
• 10: V. Srinivasan , Chan Su Park , Dae Ryun Chang, An Approach to the Measurement, Analysis, and Prediction of Brand Equity and Its Sources, Management Science, v.51 n.9, p.1433-1448, September 2005 [doi>10.1287/mnsc.1050.0405]
• 11: Gerhard J. Woeginger, On-line scheduling of jobs with fixed start and end times, Theoretical Computer Science, v.130 n.1, p.5-16, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90150-3]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  J. Computer Applications
  J.m MISCELLANEOUS

General Terms:
Algorithms, Experimentation

Keywords:
display advertising, modeling, online algorithms, optimization, simulation