## 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)})$$.

### MSC:

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

### Keywords:

budgeted maximum coverage problem
Full Text: