DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.64

Tight Approximation for Partial Vertex Cover with Hard Capacities

Authors: Jia-Yau Shiau, Mong-Jen Kao, Ching-Chi Lin, and D. T. Lee

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

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+epsilon) 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.

Cite as

Jia-Yau Shiau, Mong-Jen Kao, Ching-Chi Lin, and D. T. Lee. Tight Approximation for Partial Vertex Cover with Hard Capacities. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 64:1-64:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{shiau_et_al:LIPIcs.ISAAC.2017.64,
  author =	{Shiau, Jia-Yau and Kao, Mong-Jen and Lin, Ching-Chi and Lee, D. T.},
  title =	{{Tight Approximation for Partial Vertex Cover with Hard Capacities}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{64:1--64:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.64},
  URN =		{urn:nbn:de:0030-drops-82694},
  doi =		{10.4230/LIPIcs.ISAAC.2017.64},
  annote =	{Keywords: Approximation Algorithm, Capacitated Vertex Cover, Hard Capacities}
}

Search Results

Documents authored by Shiau, Jia-Yau

Tight Approximation for Partial Vertex Cover with Hard Capacities

Abstract

Cite as

Thanks for your feedback!

Could not send message