Document Open Access Logo

Some Results on Approximability of Minimum Sum Vertex Cover

Author Aleksa Stanković

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.50.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

Aleksa Stanković
  • Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden

Funding

Research supported by the Approximability and Proof Complexity project funded by the Knut and Alice Wallenberg Foundation.

Acknowledgements

Author thanks Johan Håstad for fruitful discussion, as well as Hans Oude Groeniger and anonymous reviewers for useful comments which improved the presentation of this work.

Cite AsGet BibTex

Aleksa Stanković. Some Results on Approximability of Minimum Sum Vertex Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.50

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Hardness of approximation
  • approximability
  • approximation algorithms
  • Label Cover
  • Unique Games Conjecture
  • Vertex Cover

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, May 1998. URL: https://doi.org/10.1145/278298.278306.
  2. Per Austrin. Balanced max 2-sat might not be the hardest. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 189-197, 2007. URL: https://doi.org/10.1145/1250790.1250818.
  3. Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Better balance by being biased: A 0.8776-approximation for max bisection. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 277-294, 2013. URL: https://doi.org/10.1137/1.9781611973105.21.
  4. Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of vertex cover and independent set in bounded degree graphs. Theory Comput., 7(1):27-43, 2011. URL: https://doi.org/10.4086/toc.2011.v007a003.
  5. Per Austrin and Aleksa Stankovic. Global cardinality constraints make approximating some max-2-csps harder. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA., volume 145 of LIPIcs, pages 24:1-24:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.24.
  6. Nikhil Bansal and Subhash Khot. Optimal long code test with one free bit. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 453-462. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.23.
  7. Uri Barenholz, Uriel Feige, and David Peleg. Improved approximation for min-sum vertex cover. Technical report, MCS06-07, Computer Science and Applied Mathematics, 2006. Google Scholar
  8. Vaggos Chatziafratis, Neha Gupta, and Euiwoong Lee. Inapproximability for local correlation clustering and dissimilarity hierarchical clustering. CoRR, abs/2010.01459, 2020. URL: http://arxiv.org/abs/2010.01459.
  9. Uriel Feige, László Lovász, and Prasad Tetali. Approximating min sum set cover. Algorithmica, 40(4):219-234, 2004. URL: https://doi.org/10.1007/s00453-004-1110-5.
  10. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 767-775, 2002. URL: https://doi.org/10.1145/509907.510017.
  11. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable csps? SIAM J. Comput., 37(1):319-357, 2007. URL: https://doi.org/10.1137/S0097539705447372.
  12. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, page 379, 2003. URL: https://doi.org/10.1109/CCC.2003.1214437.
  13. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.019.
  14. Michael Lewin, Dror Livnat, and Uri Zwick. Improved rounding techniques for the MAX 2-sat and MAX DI-CUT problems. In Integer Programming and Combinatorial Optimization, 9th International IPCO Conference, Cambridge, MA, USA, May 27-29, 2002, Proceedings, pages 67-82, 2002. URL: https://doi.org/10.1007/3-540-47867-1_6.
  15. Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 245-254, 2008. URL: https://doi.org/10.1145/1374376.1374414.
  16. Aleksa Stankovic. On regularity of max-csps and min-csps. Inf. Process. Lett., 176:106244, 2022. URL: https://doi.org/10.1016/j.ipl.2022.106244.
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