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

DOI10.1145/2933057.2933086MaRDI QIDQ5361909zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, Gregory Schwartzman, 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 algorithmdistributed graph algorithmlocal ratiovertex cover

Mathematics Subject Classification ID

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

Abstract: We present a simple deterministic distributed $(2+epsilon)$-approximation algorithm for minimum weight vertex cover, which completes in $O(logDelta/epsilonloglogDelta)$ rounds, where $Delta$ is the maximum degree in the graph, for any $epsilon>0$ which is at most $O(1)$. For a constant $epsilon$, this implies a constant approximation in $O(logDelta/loglogDelta)$ rounds, which contradicts the lower bound of [KMW10].

Recommendations

• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• Approximated distributed minimum vertex cover algorithms for bounded degree graphs
• Tight bounds on the round complexity of the distributed maximum coverage problem
• Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
• A (2-)-approximation ratio for vertex cover problem on special graphs
• Nearly optimal distributed edge coloring in O(log log n) rounds
• scientific article; zbMATH DE number 1594511
• On the approximability of the vertex cover and related problems

Cited in

(25)

• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• Parallel approximation for partial set cover
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• On the distributed decision-making complexity of the minimum vertex cover problem
• Approximated distributed minimum vertex cover algorithms for bounded degree graphs
• A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• Distributed weighted vertex cover via maximal matchings
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Fast Distributed Approximation for Max-Cut
• Distributed set cover approximation: primal-dual with optimal locality
• Optimal Distributed Covering Algorithms
• Distributed and parallel algorithms for weighted vertex cover and other covering problems
• What cannot be computed locally!
• A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks
• Computing and Combinatorics
• Distributed distance-r covering problems on sparse high-girth graphs
• Distributed distance-\(r\) covering problems on sparse high-girth graphs
• Self-stabilizing vertex cover in anonymous networks with optimal approximation ratio
• Optimal distributed covering algorithms
• Parameterized distributed algorithms
• Approximating bipartite minimum vertex cover in the Congest model
• A simple local 3-approximation algorithm for vertex cover

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361909)