Approximate Set Covering in Uniform Hypergraphs
Approximate Set Covering in Uniform Hypergraphs
复制标题
均匀超图中的近似集覆盖
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Michael Krivelevich
中科院分区：
文献类型：
--
作者：
Michael Krivelevich
考虑了r-一致超图类中的加权集覆盖问题。我们基于Aharoni，Holzman和Krivelevich最近关于整数和分数覆盖数之比的结果，提出了一种新的方法。该方法应用于最大度界为？的超图，得到了一个逼近比为(1？c/？1/(r？1))的算法。接下来，我们将这种方法与Bar-Yehuda局部比率定理的改进相结合，甚至对超图也是如此，并给出了一个基于子超图排除的近似算法的一般框架。描述了该方案的一个应用，给出了一个超图顶点逼近比为(1？C/n(r？1)/r)的算法。我们还讨论了这种方法的局限性。
The weighted set covering problem, restricted to the class ofr-uniform hypergraphs, is considered. We propose a new approach, based on a recent result of Aharoni, Holzman, and Krivelevich about the ratio of integer and fractional covering numbers ink-colorabler-uniform hypergraphs. This approach, applied to hypergraphs of maximal degree bounded by ?, yields an algorithm with approximation ratior(1?c/?1/(r?1)). Next, we combine this approach with an adaptation of the local ratio theorem of Bar-Yehuda and Even for hypergraphs and present a general framework of approximation algorithms, based on subhypergraph exclusion. An application of this scheme is described, providing an algorithm with approximation ratior(1?c/n(r?1)/r) for hypergraphs onnvertices. We discuss also the limitations of this approach.