On approximation of the vertex cover problem in hypergraphs

被引：0

作者：

Okun, Michael ^{[1
]}

机构：

[1] School of Computer Science, The Hebrew University of Jerusalem

来源：

Discrete Optimization | 2005年 / 2卷 / 01期

关键词：

Approximation algorithms; Combinatorial optimization; Set cover; Vertex cover;

D O I：

10.1016/j.disopt.2004.11.002

中图分类号：

学科分类号：

摘要：

This paper deals with approximation of the vertex cover problem in hypergraphs with bounded degree and bounded number of neighboring vertices. For hypergraphs with edges of size at most r and degree bounded by Δ we extend a result of Krivelevich and obtain a ⌈βr⌉ approximation algorithm, where 0<β<1 satisfies 1-β=[βr/(βr+1)] Δ-1/βr. In particular, we show that when (logΔ)/r≥1-1/e the approximation guarantee of our algorithm is better than that of the greedy algorithm. For hypergraphs in which each vertex has at most D adjacent vertices and its degree is bounded by Δ≥D, we show that the greedy heuristic provides an H(Δ,D)≤(D-1)[1-Δ1/(1-D)]+1 approximation, which in some cases significantly improves the well known H(Δ)≤logΔ+1 bound. © 2005 Elsevier B.V. All rights reserved.

引用

页码：101 / 111

页数：10

共 10 条

[1]

Aharoni R., Holzman R., Krivelevich M., On a theorem of Lovasz on covers in r-partite hypergraphs, Combinatorica, 16, 2, pp. 149-174, (1996)

[2]

Caro Y., Tuza Z., Improved lower bounds on k-independence, J. Graph Theory, 15, pp. 99-107, (1991)

[3]

Chvatal V., A greedy heuristic for the set-covering problem, Math. Oper. Res., 4, 3, pp. 233-235, (1979)

[4]

Furedi Z., Th. 6.19 in Matchings and covers in hypergraphs, Graphs Combinat., 4, pp. 115-206, (1988)

[5]

Halperin E., Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs, SIAM J. Comput., 31, 5, pp. 1608-1623, (2002)

[6]

Hochbaum D.S., Approximation Algorithms for NP-hard Problems, (1997)

[7]

Krivelevich M., Approximate set covering in uniform hypergraphs, J. Algorithms, 25, 1, pp. 118-143, (1997)

[8]

Paschos V.T., A survey of approximately optimal solutions to some covering and packing problems, ACM Comput. Surveys, 29, 2, pp. 171-209, (1997)

[9]

Slavik P., A tight analysis of the greedy algorithm for set cover, J. Algorithms, 25, 2, pp. 237-254, (1997)

[10]

Vazirani V.V., Approximation Algorithms, (2001)

← 1 →