Efficient scheduling of Internet banner advertisements

ABSTRACT

Despite the slowdown in the economy, advertisement revenue remains a significant source of income for many Internet-based organizations. Banner advertisements form a critical component of this income, accounting for 40 to 50 percent of the total revenue. There are considerable gains to be realized through the efficient scheduling of banner advertisements. This problem has been observed to be intractable via traditional optimization techniques, and has received only limited attention in the literature. This paper presents a procedure to generate advertisement schedules under the most commonly used advertisement pricing scheme---the CPM model. The solution approach is based on Lagrangean decomposition and is seen to provide extremely good advertisement schedules in a relatively short period of time, taking only a few hundred seconds of elapsed time on a 450 MHz PC compared to a few thousand seconds of CPU time on a workstation that other approaches need. Additionally, this approach can be incorporated into an actual implementation with minimal alterations and hence is of particular interest.

REFERENCES

• 1: Adler, M., Gibbons, P., and Matias, Y. 2002. Scheduling Space Sharing for Internet Advertising. J. Sched. 5, 2, 103--119.
• 2: Balas, E. and Zemel, E. 1980. An Algorithm for Large Zero--One Knapsack Problems. Oper. Res. 28, 1130--1154.
• 3: Cynthia Barnhart , Ellis L. Johnson , George L. Nemhauser , Martin W. P. Savelsbergh , Pamela H. Vance, Branch-And-Price: Column Generation for Solving Huge Integer Programs, Operations Research, v.46 n.3, p.316-329, March 1998 [doi>10.1287/opre.46.3.316]
• 4: Mokhtar S. Bazaraa , John J. Jarvis , Hanif D. Sherali, Linear programming and network flows (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1990
• 5: Buchwalter, C., Ryan, M., and Martin, D. 2001. The State of Online Advertising: Data Covering Fourth Quarter 2000. Tech. rep., AdRelevance (A Jupiter Media Metrix company). February.
• 6: Everett III, H. 1963. Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources. Oper. Res. 11, 399--417.
• 7: Fisher, M. 1981. The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science 27, 1--18.
• 8: Garey, M. and Graham, R. 1975. Bounds for Multiprocessor Scheduling with Resource Constraints. SIAM J. Comput. 4, 2, 187--200.
• 9: Geoffrion, A. 1974. Lagrangean Relaxation for Integer Programming. Mathematical Programming Study 2, 82--114.
• 10: Monique Guignard , Siwhan Kim, Lagrangean decomposition: A model yielding stronger lagrangean bounds, Mathematical Programming: Series A and B, v.39 n.2, p.215-228, November 1, 1987 [doi>10.1007/BF02592954]
• 11: Haney, K. 2001. Online Ad Spending Rakes in $2 Billion. eBiz Daily, April 06, 2001. http://www.digitrends.net/ebna/index_11402.html.
• 12: Held, M. and Karp, R. 1970. The Traveling Salesman Problem and Minimum Spanning Trees. Oper. Res. 18, 1138--1162.
• 13: Held, M. and Karp, R. 1971. The Traveling Salesman Problem and Minimum Spanning Trees: Part II. Mathematical Programming 1, 6--25.
• 14: ILOG, Inc. 2001. CPLEX 7.5 User's Manual. ILOG, Inc., Gentilly, France.
• 15: Interactive Advertising Beureau Internet Ad Revenue Report. Fourth Quarter of 2000, April, 2001. http://www.iab.net/forms/qreport.html.
• 16: Kumar, S., Jacob, V., and Sriskandarajah, C. 2000. Scheduling Advertising at a Web Site. In 10th Annual Workshop On Information Technologies and Systems. Sydney, Australia.
• 17: Kumar, S., Jacob, V., and Sriskandarajah, C. 2001a. Hybrid Genetic Algorithms for Scheduling Advertising on a Web Page. In Proceedings of the Twenty-Second International Conference on Information Systems (ICIS). New Orleans, LA.
• 18: Kumar, S., Jacob, V., and Sriskandarajah, C. 2001b. Scheduling Advertisements on a Web Page to Maximize Space Utilization. Working Paper. School of Management, The University of Texas at Dallas.
• 19: Marc Langheinrich , Atsuyoshi Nakamura , Naoki Abe , Tomonari Kamba , Yoshiyuki Koseki, Unintrusive customization techniques for Web advertising, Proceeding of the eighth international conference on World Wide Web, p.1259-1272, May 1999, Toronto, Canada
• 20: LINDO Systems, Inc. 2001. LINDO Callable Library User's Manual. LINDO Systems, Inc.
• 21: Martello, S., Pisinger, D., and Toth, P. 2000. New Trends in Exact Algorithms for the 0--1 Knapsack Problem. Europ. J. Oper. Res. 123, 325--332.
• 22: Martin, R. 1999. Large Scale Linear and Integer Programming : A Unified Approach. Kluwer Academic Press, Boston, MA.
• 23: Syam Menon , Linus Schrage, Order Allocation for Stock Cutting in the Paper Industry, Operations Research, v.50 n.2, p.324-332, March 2002 [doi>10.1287/opre.50.2.324.427]
• 24: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 25: Pinedo, M. 1995. Scheduling Theory, Algorithms and Systems. Prentice Hall, New Jersey.
• 26: Pisinger, D. 1997. A Minimal Algorithm for the 0--1 Knapsack Problem. Oper. Res. 45, 758--767.
• 27: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Management

Keywords:
WWW, banner advertising, scheduling