Scheduling Advertisements on a Web Page: New and Improved Approximation Algorithms
- Additional Document Info
- View All
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.
author list (cited authors)
Dawande, M., Kumar, S., & Sriskandarajah, C.
complete list of authors
Dawande, Milind||Kumar, Subodha||Sriskandarajah, Chelliah