The budgeted maximum coverage problem

Samir Khuller, Anna Moss*, Joseph Naor

*Corresponding author for this work

Research output: Contribution to journalArticle

504 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
StatePublished - Apr 16 1999

    Fingerprint

Keywords

  • Algorithms
  • Maximum coverage problem
  • Performance guarantee

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this