O(f) bi-approximation for capacitated covering with hard capacities

Mong Jen Kao, Hai Lun Tu, D. T. Lee

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

2 Scopus citations

Abstract

We consider capacitated vertex cover 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 edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset such that the demands of the edges can be covered by the capacities of the vertices and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an O(f) bi-approximation for VC-HC that gives a trade-off on the number of augmented multiplicity and the cost of the resulting cover. In particular, we show that, by augmenting the available multiplicity by a factor of k ≥ 2, a cover with a cost ratio of (1 + 1/k-1) (f - 1) to the optimal cover for the original instance can be obtained. This improves over a previous result, which has a cost ratio of f2 via augmenting the available multiplicity by a factor of f.

Original languageEnglish
Title of host publication27th International Symposium on Algorithms and Computation, ISAAC 2016
EditorsSeok-Hee Hong
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages40.1-40.12
ISBN (Electronic)9783959770262
DOIs
StatePublished - 1 Dec 2016
Event27th International Symposium on Algorithms and Computation, ISAAC 2016 - Sydney, Australia
Duration: 12 Dec 201614 Dec 2016

Publication series

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

Conference

Conference27th International Symposium on Algorithms and Computation, ISAAC 2016
Country/TerritoryAustralia
CitySydney
Period12/12/1614/12/16

Keywords

  • Bi-criteria approximation
  • Capacitated covering
  • Hard capacities

Fingerprint

Dive into the research topics of 'O(f) bi-approximation for capacitated covering with hard capacities'. Together they form a unique fingerprint.

Cite this