The budgeted maximum coverage problem. (English) Zbl 1002.68203

Summary: 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 \(S'\) of \(S\) such that the total cost of the sets in \(S'\) does not exceed \(L\), and the total weight of the 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 \(\text{NP}\subseteq\text{DTIME}(n^{O(\log\log n)})\).


68W25 Approximation algorithms
68W40 Analysis of algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI