Scheduling web banner advertisements with multiple display frequencies

Online advertising continues to be a significant source of income for many Internet-based organizations. Recent indications of improved economic growth are having an impact on advertisement revenue, with the estimated online advertising revenue in the United States for the fourth quarter of 2003 totaling a record of $2.2 billion. A substantial portion of this income comes from banner advertisements, and efficient scheduling of these advertisements could result in a considerable increase in profits. The problem of scheduling banner advertisements has been observed to be intractable via traditional optimization techniques and has received only limited attention in the literature. In addition, all past attempts to address this problem have been based on an "all-or-nothing" framework, where a customer specifies the exact number of copies of the ad to be displayed over the planning horizon, if it is selected for display by the provider of the advertisement space. This paper extends it to a more realistic setting, where the customer is allowed to specify a set of acceptable display frequencies. The Lagrangian decomposition-based solution approaches presented in this paper are observed to provide good schedules in a reasonable period of time.