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

abstract

• 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.

authors

• Sriskandarajah, Chelliah

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

publisher

• Elsevier  Publisher

published in

• Electronic Notes in Discrete Mathematics  Journal

Digital Object Identifier (DOI)

• 10.1016/s1571-0653(04)00243-4

start page

• 134

end page

• 137

volume

• 7