Paper Info
Title
Iterative partial rounding for vertex cover with hard capacities
Abstract
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. We believe that our rounding technique is of independent interest when hard constraints are considered.
Year
DOI
Venue
2016
10.5555/3039686.3039860
SODA '17: Symposium on Discrete Algorithms Barcelona Spain January, 2017
Keywords
Field
DocType
Approximation algorithm, Vertex cover, Hard capacity, Iterative rounding
Discrete mathematics,Combinatorics,Algorithm design,Computer science,Constraint graph,Rounding,Vertex cover,Partition (number theory),Coin flipping,Lemma (mathematics)
Journal
Volume
Issue
ISSN
abs/1606.08667
1
0178-4617
ISBN
Citations 
PageRank 
978-1-61197-503-1
1
0.37
References 
Authors
0
1
Name
Order
Citations
PageRank
Mong-jen Kao1267.82