Scheduling space-sharing for internet advertising

This paper provides the first in-depth study of the algorithmic questions involved in the scheduling of space-sharing for Internet advertising. We consider the scheduling problem where each advertisement is specified by a geometry and a display frequency. Given a set of ads, a schedule of the ads specifies which ads are to be displayed at the same time. The objective is find a schedule of the ads such that (1) each ad is displayed with the correct frequency, (2) each ad is allocated enough space for the specified geometry, (3) all the ads to be displayed simultaneously can be arranged in the space available for advertising. We demonstrate that an optimal schedule can be determined by finding a solution to a new variant of the bin packing problem that we introduce. In this new variant, there are a number of copies of each item to be placed into the bins. In addition to the usual bin packing requirements, all copies of an item must be placed in different bins. In this paper, we provide an efficient algorithm that finds the optimal solution to a restricted version of the new bin packing problem. This algorithm also provides a 2-approximation for the unrestricted case. We then apply this approximation to the problem of scheduling space-sharing for Internet advertising. We obtain a 2-approximation to the problem of minimizing the space requirements of a given set of ads, as well as to the problem of determining the best subset of the ads that can be scheduled with a given space constraint. We also consider an on-line version of the ad scheduling problem, where requests to purchase ad space arrive sequentially and after each request arrives, a decision must be made whether or not to sell the requested space without knowledge of future requests. We provide an algorithm that makes these decisions in a manner that is the best possible for any on-line algorithm.