Khuller et al. (1999) - The Budgeted maximum coverage problem

From Online-Partizipation
Jump to navigation Jump to search

S. Khuller, A. Moss and J. S. Naor. The Budgeted maximum coverage problem. Information processing letters 70(1):39-45, Elsevier, 1999.

Summary

The authors present a generalization of the maximum coverage problem, where the total weight of covered elements by a collection of sets with individual cost is maximized, while not exceeding a given budget limit. The problem is NP-hard and two polynomial time greedy approximations are provided. One of those is shown to be a (1-1/e)-approximation, which is also argued to be best possible ratio.

BibTeX

@article{khu-mos-nao:j:budgeted-max-cover-problem,
 title={The Budgeted maximum coverage problem}, 
 author={Khuller, Samir and Moss, Anna and Naor, Joseph Seffi},
 journal={Information processing letters},
 volume={70},
 number={1},
 pages={39--45},
 year={1999},
 publisher={Elsevier}

}