Performance Bounds of Algorithms for Scheduling Advertisements on a Web Page

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.

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