Abstract
The budgeted maximum coverage problem is: given a collection S of sets with associated costs defined over a domain of weighted elements, and a budget L, find a subset of S′ ⊆ S such that the total cost of sets in S′ does not exceed L, and the total weight of elements covered by S′ is maximized. This problem is NP-hard. For the special case of this problem, where each set has unit cost, a (1 - 1/e)-approximation is known. Yet, prior to this work, no approximation results were known for the general cost version. The contribution of this paper is a (1 - 1/e)-approximation algorithm for the budgeted maximum coverage problem. We also argue that this approximation factor is the best possible, unless NP ⊆ DTIME(nO(log log n)).
| Original language | English (US) |
|---|---|
| Pages (from-to) | 39-45 |
| Number of pages | 7 |
| Journal | Information Processing Letters |
| Volume | 70 |
| Issue number | 1 |
| State | Published - Apr 16 1999 |
Fingerprint
Keywords
- Algorithms
- Maximum coverage problem
- Performance guarantee
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications
Cite this
Khuller, S., Moss, A., & Naor, J. (1999). The budgeted maximum coverage problem. Information Processing Letters, 70(1), 39-45.