O(f) Bi-criteria Approximation for Capacitated Covering with Hard Capacities

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-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-criteria 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+1k-1)(f-1) to the optimal cover for the original instance can be obtained. This improves over the previously best known guarantee, which has a cost ratio of f 2 via augmenting the available multiplicity by a factor of f.

Original languageEnglish
Pages (from-to)1800-1817
Number of pages18
JournalAlgorithmica
Volume81
Issue number5
DOIs
StatePublished - 15 May 2019

Keywords

  • Bi-criteria approximation
  • Capacitated covering
  • Hard capacities

Fingerprint

Dive into the research topics of 'O(f) Bi-criteria Approximation for Capacitated Covering with Hard Capacities'. Together they form a unique fingerprint.

Cite this