The budgeted maximum coverage problem

Samir Khuller; Anna Moss; Joseph Naor

doi:10.1016/s0020-0190(99)00031-9

The budgeted maximum coverage problem

Samir Khuller, Anna Moss^*, Joseph Naor

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

559 Scopus citations

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(n^{O(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	https://doi.org/10.1016/s0020-0190(99)00031-9
State	Published - Apr 16 1999

Keywords

Algorithms
Maximum coverage problem
Performance guarantee

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/s0020-0190(99)00031-9

Fingerprint Dive into the research topics of 'The budgeted maximum coverage problem'. Together they form a unique fingerprint.

Cite this

@article{b556b3db40964c87b8aa5a22b8cf1048,

title = "The budgeted maximum coverage problem",

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)).",

keywords = "Algorithms, Maximum coverage problem, Performance guarantee",

author = "Samir Khuller and Anna Moss and Joseph Naor",

note = "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.",

year = "1999",

month = apr,

day = "16",

doi = "10.1016/s0020-0190(99)00031-9",

language = "English (US)",

volume = "70",

pages = "39--45",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "1",

}

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 -

The budgeted maximum coverage problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this