TY - JOUR

T1 - Approximation Algorithm for Vertex Cover with Multiple Covering Constraints

AU - Hung, Eunpyeong

AU - Kao, Mong Jen

N1 - Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2021

Y1 - 2021

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 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 (3 cflog r) , where c is a large constant used to ensure a low failure probability for Monte-Carlo randomized algorithms. Compared to the 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 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 (3 cflog r) , where c is a large constant used to ensure a low failure probability for Monte-Carlo randomized algorithms. Compared to the 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.

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

U2 - 10.1007/s00453-021-00885-w

DO - 10.1007/s00453-021-00885-w

M3 - Article

AN - SCOPUS:85118205231

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

ER -