A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds

DOI10.1145/2933057.2933086zbMath1376.68155arXiv1602.03713OpenAlexW2403340448MaRDI QIDQ5361909

Gregory Schwartzman, Keren Censor-Hillel, Reuven Bar Yehuda

Publication date: 29 September 2017

Published in: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.03713

zbMATH Keywords

approximation algorithmvertex coverlocal ratiodistributed graph algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (5)

Fast Distributed Approximation for Max-Cut ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Parallel approximation for partial set cover ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs

This page was built for publication: A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds