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

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}

}