Scheduling online advertisements to maximize revenue under variable display frequency

The online advertising industry realized annual revenues estimated at over $26 billion, in the United States alone, in 2010. Banner advertising accounts for an estimated 23% of all online advertising revenues. Publishers of banner advertisements face a scheduling optimization problem on a daily basis. Several papers in the literature have proposed mathematical models and solution approaches to address a publisher's banner advertisement scheduling problem and the problem has been shown to be NP-hard. In this paper we propose a new model variation for the problem, which incorporates variable display frequencies. We find that the variable-display frequency model provides significantly improved space utilization relative to the fixed-display frequency model and consequently higher revenues for the publishers.