Iterative Partial Rounding for Vertex Cover with Hard Capacities

Mong Jen Kao*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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. (In: SODA’14, 2014) to the tight extent. This also closes the gap of approximation since it was posted by Chuzhoy and Naor (Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS) 2002, pp. 481--489. IEEE Computer Society, 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.

Original languageEnglish
Pages (from-to)45-71
Number of pages27
JournalAlgorithmica
Volume83
Issue number1
DOIs
StatePublished - Jan 2021

Keywords

  • Approximation algorithm
  • Hard capacity
  • Iterative rounding
  • Vertex cover

Fingerprint

Dive into the research topics of 'Iterative Partial Rounding for Vertex Cover with Hard Capacities'. Together they form a unique fingerprint.

Cite this