Optimal distributed covering algorithms

DOI10.4230/LIPICS.DISC.2019.5MaRDI QIDQ6487522zbMATH OpenFDO

Authors Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2019.5

zbMATH Keywords

approximation algorithmsdistributed algorithmsset coververtex cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25)

Recommendations

• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• Distributed set cover approximation: primal-dual with optimal locality
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• Distributed and parallel algorithms for weighted vertex cover and other covering problems

Cited in

(9)

• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• Optimal distributed covering algorithms
• Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
• 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
• Beep-and-sleep: message and energy efficient set cover
• Distributed algorithms for covering, packing and maximum weighted matching
• Approximating bipartite minimum vertex cover in the Congest model

This page was built for publication: Optimal distributed covering algorithms

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