Tight approximation for partial vertex cover with hard capacities

Jia Yau Shiau, Mong Jen Kao, Ching Chi Lin, D. T. Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

We consider the partial vertex cover problem with hard capacity constraints (Partial VC-HC) on hypergraphs. In this problem we are given a hypergraph G = (V,E) with a maximum edge size f and a covering requirement R. Each edge is associated with a demand, and each vertex is associated with a capacity and an (integral) available multiplicity. The objective is to compute a minimum vertex multiset such that at least R units of demand from the edges are covered by the capacities of the vertices in the multiset and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an f-Approximation for this problem, improving over a previous result of (2f + 2)(1 +) by Cheung et al to the tight extent possible. Our new ingredient of this work is a generalized analysis on the extreme points of the natural LP, developed from previous works, and a strengthened LP lower-bound obtained for the optimal solutions.

Original languageEnglish
Title of host publication28th International Symposium on Algorithms and Computation, ISAAC 2017
EditorsTakeshi Tokuyama, Yoshio Okamoto
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770545
DOIs
StatePublished - 1 Dec 2017
Event28th International Symposium on Algorithms and Computation, ISAAC 2017 - Phuket, Thailand
Duration: 9 Dec 201722 Dec 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume92
ISSN (Print)1868-8969

Conference

Conference28th International Symposium on Algorithms and Computation, ISAAC 2017
Country/TerritoryThailand
CityPhuket
Period9/12/1722/12/17

Keywords

  • Approximation algorithm
  • Capacitated vertex cover
  • Hard capacities

Cite this