Iterative Partial Rounding for Vertex Cover with Hard Capacities (Mong-Jen Kao)

Abstract

We consider the vertex cover problem with hard capacity constraints (VC-HC) on hypergraphs. In this problem, we are given a hypergraph G = (V,E) with a maximum edge size f. Each e∈E is associated with an edge demand d and each v ∈ V is associated with a capacity c and an available multiplicity (the number of available copies) m. The objective is to find a minimum-size vertex cover, a vertex multi-set represented by an assignment function, such that the demands of the edges can be covered by the capacities of the vertices chosen in the multiset and the multiplicity of each vertex does not exceed its available multiplicity.

We provide a simple and novel algorithmic design technique, for which we call iterative partial rounding, that gives a tight rounding-based approximation for vertex cover with hard capacities (VC-HC). In particular, we obtain an f-approximation for VC-HC on hypergraphs, improving over a previous results of Cheung et al (SODA 2014) to the tight extent. This also closes the gap of approximation since it was posted by Chuzhoy and Naor in (FOCS 2002).

Our main technical tool for establishing the approximation guarantee is a separation lemma that certifies the existence of a strong partition for solutions that are basic feasible in an extended version of the natural LP.

Time

Speaker

Room