The budgeted maximum coverage problem

Samir Khuller, Anna Moss*, Joseph Naor

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

787 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(nO(log log n)).

Original languageEnglish (US)
Pages (from-to)39-45
Number of pages7
JournalInformation Processing Letters
Volume70
Issue number1
DOIs
StatePublished - 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

Fingerprint

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

Cite this