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 a..