Abstract
Free services to internet users are commonly available on many web sites e.g., Hotmail and Yahoo. For such sites, revenue generated from advertisements (hereafter also called “ads”) placed on the web pages is critical for survival. An effective way to schedule ads on web pages to optimize certain performance measures is an important problem that these sites need to address.
In this note, we report improved approximation algorithms for the following problem: ads from a set of n ads A = {A i ,...,A n } are to be placed on a web page during a planning horizon that is divided into N time intervals. In each time interval, ads are shown in a rectangular space called a slot. An ad A i is specified by its size s i and frequency w i and is to be scheduled in exactly w i slots. We are required to find a schedule that minimizes the maximum fullness among all the slots, where the fullness of a slot is the sum of the sizes of ads scheduled in that slot. Our results include (i) the first online algorithm with a performance bound of \(2 - \frac{1}{N}\), and (ii) two offline algorithms with performance guarantees of \(1 + 1\frac{1}{\sqrt{2}}\) and \(\frac{3}{2}\), respectively. These bounds are significant improvements over those for previously known algorithms presented in Adler, Gibbons, and Matias (2002) and Dawande, Kumar, and Sriskandarajah (2003).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Adler, M., P. B. Gibbons, and Y. Matias, “Scheduling space-sharing for internet advertising,” Journal of Scheduling, 5(2), 103–119 (2002).
Albers, S., “Better bounds for online scheduling,” SIAM Journal on Computing, 29(2), 459–473 (1999).
Bartal, Y., A. Fiat, H. Karloff, and R. Vohra, “New algorithms for an ancient scheduling problem,” Journal of Computer and System Sciences, 51, 359–366 (1995).
Chandrasekaran, R., B. Chen, G. Galambos, P. R. Narayanan, A. van Vilet, and G. J. Woeginger, “A note on’ and on-line scheduling heuristic with better worst case ratio than Graham’s list scheduling,” SIAM Journal on Computing, 26(3), 870–872 (1997).
Coffman, Jr., E. G., M. R. Garey, and D. S. Johnson, “An application of bin-packing to multiprocessor scheduling,” SIAM Journal of Computing, 7(1), 1–17 (1978).
Dawande, M., S. Kumar, and C. Sriskandarajah, “Performance bounds of algorithms for scheduling advertisements on a web page,” Journal of Scheduling, 6, 373–393 (2003).
Fleischer, R. and M. Wahl, “On-line scheduling revisited,” Journal of Scheduling, 3(6), 343–353 (2000).
Friesen, D. K., “Tighter bounds for multifit processor scheduling algorithm,” SIAM Journal of Computing, 13, 170–181 (1984).
Friesen, D. K. and M. A. Langston, “Evaluation of a multifit-based scheduling algorithm,” Journal of Algorithms, 7, 35–59 (1986).
Fruend, A. and J. Naor, “Approximating the advertisement placement problem,” Journal of Scheduling, 7, 365–374 (2004).
Galambos, G. and G. J. Woeginger, “An on-line scheduling heuristic with better worst case ratio than Graham’s list scheduling,” SIAM Journal on Computing, 22(2), 349–355 (1993).
Graham, R. L., “Bounds onmultiprocessing timing anomalies,” SIAM Journal of Applied Mathematics, 17, 416–429 (1969).
Graham, R. L., “Bounds on multiprocessing timing anomalies,” SIAM Journal of Applied Mathematics, 17, 416–429 (1969).
Hyland, T. “Why Internet advertising?” in Webvertising: The Ultimate Internet Advertising Guide, SCN Education B. V., Friedrich Viewag & Sohn, 2000, pp. 13–18.
Interactive Advertising Bureau, http://www.iab.net.
Karger, D. R., S. J. Phillips, and E. Torng, “A better algorithm for an ancient scheduling problem,” Journal of Algorithms, 20(2), 400–430 (1996).
Martin, R. K., Large Scale Linear and Integer Optimization, Kluwer, Massachusetts, 1999.
Puetz, J., “A revolution in our midst,” Satellite Communications Atlanta, 24, 38 (2000).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
DAWANDE, M., KUMAR, S. & SRISKANDARAJAH, C. Scheduling Web Advertisements: A Note on the Minspace Problem. J Sched 8, 97–106 (2005). https://doi.org/10.1007/s10951-005-5217-6
Issue Date:
DOI: https://doi.org/10.1007/s10951-005-5217-6