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 |
DOIs | |
State | Published - Apr 16 1999 |
Funding
∗Corresponding author. Email: [email protected]. 1Email: [email protected]. Research supported by NSF CAREER Award CCR-9501355. 2Email: [email protected]. This research was supported by Technion V.P.R. Fund 120-938 – New York Metropolitan Research Fund.
Keywords
- Algorithms
- Maximum coverage problem
- Performance guarantee
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications