TY - GEN

T1 - Approximation algorithm for vertex cover with multiple covering constraints

AU - Hong, Eunpyeong

AU - Kao, Mong Jen

N1 - Publisher Copyright:
© Eunpyeong Hong and Mong-Jen Kao; licensed under Creative Commons License CC-BY

PY - 2018/12/1

Y1 - 2018/12/1

N2 - We consider the vertex cover problem with multiple coverage constraints in hypergraphs. In this problem, we are given a hypergraph G = (V, E) with a maximum edge size f, a cost function w : V → Z+, and edge subsets P1, P2, . . ., Pr of E along with covering requirements k1, k2, . . ., kr for each subset. The objective is to find a minimum cost subset S of V such that, for each edge subset Pi, at least ki edges of it are covered by S. This problem is a basic yet general form of classical vertex cover problem and a generalization of the edge-partitioned vertex cover problem considered by Bera et al. We present a primal-dual algorithm yielding an (f · Hr + Hr)-approximation for this problem, where Hr is the rth harmonic number. This improves over the previous ratio of (3cf log r), where c is a large constant used to ensure a low failure probability for Monte-Carlo randomized algorithms. Compared to previous result, our algorithm is deterministic and pure combinatorial, meaning that no Ellipsoid solver is required for this basic problem. Our result can be seen as a novel reinterpretation of a few classical tight results using the language of LP primal-duality.

AB - We consider the vertex cover problem with multiple coverage constraints in hypergraphs. In this problem, we are given a hypergraph G = (V, E) with a maximum edge size f, a cost function w : V → Z+, and edge subsets P1, P2, . . ., Pr of E along with covering requirements k1, k2, . . ., kr for each subset. The objective is to find a minimum cost subset S of V such that, for each edge subset Pi, at least ki edges of it are covered by S. This problem is a basic yet general form of classical vertex cover problem and a generalization of the edge-partitioned vertex cover problem considered by Bera et al. We present a primal-dual algorithm yielding an (f · Hr + Hr)-approximation for this problem, where Hr is the rth harmonic number. This improves over the previous ratio of (3cf log r), where c is a large constant used to ensure a low failure probability for Monte-Carlo randomized algorithms. Compared to previous result, our algorithm is deterministic and pure combinatorial, meaning that no Ellipsoid solver is required for this basic problem. Our result can be seen as a novel reinterpretation of a few classical tight results using the language of LP primal-duality.

KW - And phrases Vertex cover

KW - Approximation algorithm

KW - Multiple cover constraints

UR - http://www.scopus.com/inward/record.url?scp=85060609197&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2018.43

DO - 10.4230/LIPIcs.ISAAC.2018.43

M3 - Conference contribution

AN - SCOPUS:85060609197

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 43:1-43:11

BT - 29th International Symposium on Algorithms and Computation, ISAAC 2018

A2 - Liao, Chung-Shou

A2 - Hsu, Wen-Lian

A2 - Lee, Der-Tsai

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 29th International Symposium on Algorithms and Computation, ISAAC 2018

Y2 - 16 December 2018 through 19 December 2018

ER -