1 Search Results for "Hong, Eunpyeong"

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.43
Approximation Algorithm for Vertex Cover with Multiple Covering Constraints

Authors: Eunpyeong Hong and Mong-Jen Kao

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We consider the vertex cover problem with multiple coverage constraints in hypergraphs. In this problem, we are given a hypergraph G=(V,E) with a maximum edge size f, a cost function w: V - > Z^+, and edge subsets P_1,P_2,...,P_r of E along with covering requirements k_1,k_2,...,k_r for each subset. The objective is to find a minimum cost subset S of V such that, for each edge subset P_i, at least k_i edges of it are covered by S. This problem is a basic yet general form of classical vertex cover problem and a generalization of the edge-partitioned vertex cover problem considered by Bera et al. We present a primal-dual algorithm yielding an (f * H_r + H_r)-approximation for this problem, where H_r is the r^{th} harmonic number. This improves over the previous ratio of (3cf log r), where c is a large constant used to ensure a low failure probability for Monte-Carlo randomized algorithms. Compared to previous result, our algorithm is deterministic and pure combinatorial, meaning that no Ellipsoid solver is required for this basic problem. Our result can be seen as a novel reinterpretation of a few classical tight results using the language of LP primal-duality.
Cite as

Eunpyeong Hong and Mong-Jen Kao. Approximation Algorithm for Vertex Cover with Multiple Covering Constraints. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 43:1-43:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hong_et_al:LIPIcs.ISAAC.2018.43,
  author =	{Hong, Eunpyeong and Kao, Mong-Jen},
  title =	{{Approximation Algorithm for Vertex Cover with Multiple Covering Constraints}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{43:1--43:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.43},
  URN =		{urn:nbn:de:0030-drops-99919},
  doi =		{10.4230/LIPIcs.ISAAC.2018.43},
  annote =	{Keywords: Vertex cover, multiple cover constraints, Approximation algorithm}
}
  • Refine by Author
  • 1 Hong, Eunpyeong
  • 1 Kao, Mong-Jen

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Vertex cover
  • 1 multiple cover constraints

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact