The budgeted maximum coverage problem

被引：631

作者：

Khuller, S

Moss, A ^{[1
]}

Naor, JS

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

[2] Univ Maryland, Dept Comp Sci, College Pk, MD 20742 USA

来源：

INFORMATION PROCESSING LETTERS | 1999年 / 70卷 / 01期

关键词：

algorithms; maximum coverage problem; performance guarantee;

D O I：

10.1016/S0020-0190(99)00031-9

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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' subset of or equal to S such that the total cost of sets in S' does not exceed L, and the total weight of elements covered by SI 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 subset of or equal to DTIME(n(O(log log n))). (C) 1999 Published by Elsevier Science B.V. All rights reserved.

引用

页码：39 / 45

页数：7

共 11 条

[1] OPTIMAL LOCATION OF DISCRETIONARY SERVICE FACILITIES [J].