DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.40

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

Authors: Mong-Jen Kao, Hai-Lun Tu, and D. T. Lee

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

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 geq 2, a cover with a cost ratio of (1+ frac{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 f^2 via augmenting the available multiplicity by a factor of f.

Cite as

Mong-Jen Kao, Hai-Lun Tu, and D. T. Lee. O(f) Bi-Approximation for Capacitated Covering with Hard Capacities. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 40:1-40:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kao_et_al:LIPIcs.ISAAC.2016.40,
  author =	{Kao, Mong-Jen and Tu, Hai-Lun and Lee, D. T.},
  title =	{{O(f) Bi-Approximation for Capacitated Covering with Hard Capacities}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{40:1--40:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.40},
  URN =		{urn:nbn:de:0030-drops-68102},
  doi =		{10.4230/LIPIcs.ISAAC.2016.40},
  annote =	{Keywords: Capacitated Covering, Hard Capacities, Bi-criteria Approximation}
}

Search Results

Documents authored by Tu, Hai-Lun

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

Abstract

Cite as

Thanks for your feedback!

Could not send message