Scheduling Advertisements on a Web Page: New and Improved Approximation Algorithms Academic Article uri icon


  • We develop approximation algorithms for solving two problems, MINSPACE and MAXSPACE, which are shown to be strongly NP-Hard [2]. 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.

published proceedings

  • Electronic Notes in Discrete Mathematics

author list (cited authors)

  • Dawande, M., Kumar, S., & Sriskandarajah, C.

citation count

  • 0

complete list of authors

  • Dawande, Milind||Kumar, Subodha||Sriskandarajah, Chelliah

publication date

  • April 2001