Scheduling Space-Sharing for Internet Advertising

Ther has recently been an enormous increase in the volume of advertisements appearing on the internet. The existing technology allows great flexibility in how these ads can be placed, but this leads to new scheduling problems that do not arise in more conventional forms of advertising. This paper describes new algorithms and hardness results for some of these scheduling problems. We consider a scenario where the advertisements are specified in terms of three parameters: the user frequency, or the fraction of accesses by users that see and ad at some point during tghe access, the time frequency, or the fraction of the time that the provider displays the ad to any user that sees the ad, and the ad geometry. Given a set of ads with these constraints, we wish to find a schedule that uses only a fixed amount of advertising space. WE here address the problem of finding a valid schedule of the entire set of ads, as well as the problem of determining the maximum subset of the ads that can be scheduled. We show that both problems are NP-Hard, given an arbitrary set of ads. However, we also show how to find a valid schedule when the allowed geometries of the ads are slightly restricted. In some scenarios, this leads to a 2-approximation of the case where the ad geometrices are unrestricted. We also give 2-approximation for the problem of finding the maximum subset of the ads that can be scheduled. We then consider the on-line scheduling problem, where ads arrive dynamically and after each ad arrives, we must decide whether or not to accept the ad. Given an upper bound on the size of an ad, we shoe hoe to make these decisions in a manner that is close to optimal in terms of this upper bound on ad size.