Scheduling Advertisements on a Web Page: New and Improved Approximation Algorithms
Additional Document Info
We develop approximation algorithms for solving two problems, MINSPACE and MAXSPACE, which are shown to be strongly NP-Hard . For the MINSPACE problem, two algorithms are provided: one with a performance guarantee of 2 and the other with a performance guarantee better than 2. For the MAXSPACE problem, two algorithms are developed with performance guarantees of 1/4 and 3/10.