The budgeted maximum coverage problem
The budgeted maximum coverage problem
复制标题
DOI：
10.1016/s0020-0190(99)00031-9
复制
发表时间：
1999-04-16
影响因子：
0.5
通讯作者：
Naor, JS
中科院分区：
文献类型：
--
作者：
Khuller, S;Moss, A;Naor, JS
预算最大覆盖问题是：给定集合 S 的集合 S，其相关成本在加权元素域上定义，并且预算 L，找到 S' 的子集等于或等于 S 的子集，使得 S' 中的集合的总成本不超过 L，并且 SI 覆盖的元素的总权重最大化。这个问题是NP困难的。对于该问题的特殊情况，其中每组都有单位成本，(1 - 1/e) 近似值是已知的。然而，在这项工作之前，尚无通用成本版本的近似结果。本文的贡献是针对预算最大覆盖问题的 (1 - 1/e) 近似算法。我们还认为，这个近似因子是最好的，除非 NP 子集等于或等于 DTIME(n(O(log log n)))。 (C) 1999 年由 Elsevier Science B.V. 出版。保留所有权利。
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.