Optimal Distributed Covering Algorithms

DOI10.1145/3293611.3331577MaRDI QIDQ5145187zbMATH OpenOpenAlexWikidataFDO

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

Publication date 20 January 2021

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

Full work available at URL https://arxiv.org/abs/1902.09377, https://drops.dagstuhl.de/opus/volltexte/2019/11312/

zbMATH Keywords

distributed computinggraph algorithmsset coververtex coverprimal dual

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

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

Cited in

(6)

• Optimal distributed covering algorithms
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Parameterized analysis and crossing minimization problems
• Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
• Beep-and-sleep: message and energy efficient set cover
• scientific article; zbMATH DE number 2036580 (Why is no real title available?)

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