### 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 |

State | Published - 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

*Information Processing Letters*,

*70*(1), 39-45.