Scheduling web advertisements: a note on the minspace problem

Scheduling web advertisements: a note on the minspace problem

0.00 Avg rating0 Votes
Article ID: iaor2008757
Country: United Kingdom
Volume: 8
Issue: 1
Start Page Number: 97
End Page Number: 106
Publication Date: Jan 2005
Journal: Journal of Scheduling
Authors: , ,
Keywords: scheduling, internet
Abstract:

Free services to internet users are commonly available on many web sites, e.g., Hotmail and Yahoo. For such sites, revenue generated from advertisements (hereafter also called ‘ads’) placed on the web pages is critical for survival. An effective way to schedule ads on web pages to optimize certain performance measures is an important problem that these sites need to address. In this note, we report improved approximation algorithms for the following problem: ads from a set of n ads A = {Ai,…,An} are to be placed on a web page during a planning horizon that is divided into N time intervals. In each time interval, ads are shown in a rectangular space called a slot. An ad Ai is specified by its size si and frequency wi and is to be scheduled in exactly wi slots. We are required to find a schedule that minimizes the maximum fullness among all the slots, where the fullness of a slot is the sum of the sizes of ads scheduled in that slot. Our results include (i) the first online algorithm with a performance bound of 2− 1/N, and (ii) two offline algorithms with performance guarantees of 1 + 1/√2 and 3/2, respectively. These bounds are significant improvements over those for previously known algorithms presented by Adler et al. and Dawande et al.

Reviews

Required fields are marked *. Your email address will not be published.