A better-than-greedy approximation algorithm for the minimum set cover problem
A better-than-greedy approximation algorithm for the minimum set cover problem
复制标题
DOI：
10.1137/s0097539704444750
复制
发表时间：
2005-01-01
影响因子：
1.6
通讯作者：
Levin, A
中科院分区：
文献类型：
--
作者：
Hassin, R;Levin, A
在加权集合覆盖问题中，我们给定一组元素E = {e（1），e（2），.，e（n）}和E的子集的集合F，其中每个S是F的具有正成本c（S）的元素。问题是计算一个子集SOL，使得布尔ORS是SOL的一个元素S-j = E，并且其成本Sigma（S是SOL的一个元素）c（S）最小化。当|S|
In the weighted set-cover problem we are given a set of elements E = {e(1), e(2),..., e(n)} and a collection F of subsets of E, where each S is an element of F has a positive cost c(S). The problem is to compute a subcollection SOL such that boolean ORS is an element of SOL S-j = E and its cost Sigma(S is an element of SOL) c(S) is minimized. When |S|