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

DOI10.1145/3060294MaRDI QIDQ4640294zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, Gregory Schwartzman, Reuven Bar-Yehuda

Publication date 17 May 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3060294

zbMATH Keywords

distributed computingapproximation algorithmsgraph algorithmsvertex coverlocal ratio

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)

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 + \epsilon)\)-approximate minimum vertex cover in \(O(1/\epsilon^2)\) amortized update time
• A \((2-\varepsilon)\)-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

(24)

• Distributed weighted vertex cover via maximal matchings
• A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• A simple local 3-approximation algorithm for vertex cover
• What cannot be computed locally!
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Approximated distributed minimum vertex cover algorithms for bounded degree graphs
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• Minimum vertex cover, distributed decision-making, and communication complexity
• Improved distributed approximations for maximum independent set
• Parameterized distributed algorithms
• Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
• Optimal distributed covering algorithms
• Distributed and parallel algorithms for weighted vertex cover and other covering problems
• Distributed set cover approximation: primal-dual with optimal locality
• Computing and Combinatorics
• Optimal distributed covering algorithms
• A time hierarchy theorem for the LOCAL model
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Adapting local sequential algorithms to the distributed setting
• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds

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 Q4640294)