Abstract
We propose and evaluate a number of improvements to the linear programming formulation of web advertisement scheduling, which we have proposed elsewhere together with our colleagues [Langheinrich et al., 9]. In particular, we address a couple of important technical challenges having to do with the estimation of click-through rates and optimization of display probabilities (the exploration–exploitation trade-off and the issue of data sparseness and scalability), as well as practical aspects that are essential for successful deployment of this approach (the issues of multi-impressions and inventory management). We propose solutions to each of these issues, and assess their effectiveness by running large-scale simulation experiments.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
Abe, N. and A. Nakamura. (1999). “Learning to Optimally Schedule Internet Banner Advertisements.” In Proc. of the 16th International Conference on Machine Learning, pp. 12–21.
Bradley, G., G. Brown, and G. Graves. (1977). “Design and Implementation of a Large Scale Primal Trans-shipment Algorithm.” Management Science24, 1–34
Berry, D.A. and B. Fristedt. (1985). Bandit Problems. Chapman & Hall.
Chickering, D. and D. Heckerman. (2000). “Targeted Advertising with Inventory Management.” In Proc. of ACM Special Interest Group on E-Commerce (EC00), pp. 145–149.
Dantzig, G. (1963). Linear Programming and Extensions. Princeton University Press.
DoubleClick Inc. (2003). DoubleClick 2002 Full-Year Ad Serving Trends.
Feller, W. (1968). An Introduction to Probability Theory and its Applications, Vol. 1. Wiley, 3rd edition.
Gittins, J.C. (1988). Multi-Armed Bandit Allocation Indices. Chichester: Wiley.
Langheinrich, M., A. Nakamura, N. Abe, T. Kamba, and Y. Koseki. (1999). “Unintrusive Customization Techniques for Web Advertising.” Computer Networks31, 1259–1272.
Li, H. and N. Abe. (1998). “Word Clustering and Disambiguation Based on Co-Occurrence Data.” In Pro-ceedings of COLING-ACL, pp. 749–755.
Nakamura, A. (2002). “Improvements in Practical Aspects of Optimally Scheduling Web Advertising.” In Proc. of the 11th International World Wide Web Conference, pp. 536–541.
Nakamura, A. and N. Abe. (1998). “Collaborative Filtering Using Weighted Majority Prediction Algo-rithms.” In Proc. of the 15th International Conference on Machine Learning, pp. 395–403.
Pazzani, M. (1999). “A Framework for Collaborative, Content-Based and Demographic Filtering.” Artificial Intelligence Review13(5–6), 393–408.
Quinlan, R. (1993). C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann.
Rissanen, J. (1978). “Modeling by Shortest Data Description.” Automatica14, 37–38.
Sakamoto, Y., Y. Ishiguro, and M. Kitagawa. (1986). Akaike Information Criterion Statistics. Dordrecht: Reidel.
Tomlin, J. (2000). “An Entropy Approach to Unintrusive Targeted Advertising on the Web.” Computer Networks33, 767–774.
Ye, Y. (1997). Interior Point Algorithms: Theory and Analysis, Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: Wiley.
Author information
Authors and Affiliations
About this article
Cite this article
Nakamura, A., Abe, N. Improvements to the Linear Programming Based Scheduling of Web Advertisements. Electronic Commerce Research 5, 75–98 (2005). https://doi.org/10.1023/B:ELEC.0000045974.88926.88
Issue Date:
DOI: https://doi.org/10.1023/B:ELEC.0000045974.88926.88