TY - JOUR
T1 - The budgeted maximum coverage problem
AU - Khuller, Samir
AU - Moss, Anna
AU - Naor, Joseph
N1 - Funding Information:
∗Corresponding author. Email: annaru@cs.technion.ac.il. 1Email: samir@cs.umd.edu. Research supported by NSF CAREER Award CCR-9501355. 2Email: naor@cs.technion.ac.il. This research was supported by Technion V.P.R. Fund 120-938 – New York Metropolitan Research Fund.
PY - 1999/4/16
Y1 - 1999/4/16
N2 - 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)).
AB - 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)).
KW - Algorithms
KW - Maximum coverage problem
KW - Performance guarantee
UR - http://www.scopus.com/inward/record.url?scp=0032614948&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032614948&partnerID=8YFLogxK
U2 - 10.1016/s0020-0190(99)00031-9
DO - 10.1016/s0020-0190(99)00031-9
M3 - Article
AN - SCOPUS:0032614948
VL - 70
SP - 39
EP - 45
JO - Information Processing Letters
JF - Information Processing Letters
SN - 0020-0190
IS - 1
ER -