Consider a set of n advertisements (called ads) A=A₁, A₂, ... , A_n, competing to be placed in a planning horizon that is divided into N time intervals, called slots. An ad A_i is specified by its size s_i and frequency w_i. The size s_i represents the amount of space the ad occupies in a slot. Ad A_i is said to be scheduled if exactly w_i copies of A_i are placed in the slots, subject to the restriction that a slot contains at most one copy of an ad.

In this paper, the authors consider two problems. The first is the MINSPACE problem. In this problem, they minimize the maximum fullness among all slots in a feasible schedule, where the fullness of a slot is the sum of the sizes of all the ads assigned to the slot. The second problem is the MAXSPACE problem. In this problem, they 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 w_is_i is maximized. The authors examine the complexity status of both problems, and provide heuristics with performance guarantees.