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

SN - 0020-0190

VL - 70

SP - 39

EP - 45

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -