Performance Bounds of Algorithms for Scheduling Advertisements on a Web Page Academic Article uri icon


  • Consider a set of n advertisements (hereafter called "ads") A = {A1, . . . , An} competing to be placed in a planning horizon which is divided into N time intervals called slots. An ad Aiis specified by its size siand frequency wi. The size sirepresents the amount of space the ad occupies, in a slot. Ad Aiis said to be scheduled if exactly wicopies of Aiare placed in the slots subject to the restriction that a slot contains at most one copy of an ad. In this paper, we consider two problems. The MINSPACE problem minimizes the maximum fullness among all slots in a feasible schedule where the fullness of a slot is the sum of the sizes of ads assigned to the slot. For the MAXSPACE problem, in addition, we are given a common maximum fullness S for all slots. The total size of the ads placed in a slot cannot exceed S. The objective is to find a feasible schedule A A of ads such that the total occupied slot space AiAwisimaximized. We examine the complexity status of both problems and provide heuristics with performance guarantees.

published proceedings

  • Journal of Scheduling

author list (cited authors)

  • Dawande, M., Kumar, S., & Sriskandarajah, C.

citation count

  • 39

complete list of authors

  • Dawande, Milind||Kumar, Subodha||Sriskandarajah, Chelliah

publication date

  • July 2003