License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.50
URN: urn:nbn:de:0030-drops-171722
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17172/
Go to the corresponding LIPIcs Volume Portal

Stanković, Aleksa

Some Results on Approximability of Minimum Sum Vertex Cover

pdf-format:
LIPIcs-APPROX50.pdf (0.7 MB)

Abstract

We study the Minimum Sum Vertex Cover problem, which asks for an ordering of vertices in a graph that minimizes the total cover time of edges. In particular, n vertices of the graph are visited according to an ordering, and for each edge this induces the first time it is covered. The goal of the problem is to find the ordering which minimizes the sum of the cover times over all edges in the graph.
In this work we give the first explicit hardness of approximation result for Minimum Sum Vertex Cover. In particular, assuming the Unique Games Conjecture, we show that the Minimum Sum Vertex Cover problem cannot be approximated within 1.014. The best approximation ratio for Minimum Sum Vertex Cover as of now is 16/9, due to a recent work of Bansal, Batra, Farhadi, and Tetali.
We also revisit an approximation algorithm for regular graphs outlined in the work of Feige, Lovász, and Tetali, and show that Minimum Sum Vertex Cover can be approximated within 1.225 on regular graphs.

BibTeX - Entry

@InProceedings{stankovic:LIPIcs.APPROX/RANDOM.2022.50,
  author =	{Stankovi\'{c}, Aleksa},
  title =	{{Some Results on Approximability of Minimum Sum Vertex Cover}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{50:1--50:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17172},
  URN =		{urn:nbn:de:0030-drops-171722},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.50},
  annote =	{Keywords: Hardness of approximation, approximability, approximation algorithms, Label Cover, Unique Games Conjecture, Vertex Cover}
}

Keywords: Hardness of approximation, approximability, approximation algorithms, Label Cover, Unique Games Conjecture, Vertex Cover
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Issue Date: 2022
Date of publication: 15.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI