Hardness of Distributed Optimization

DOI10.1145/3293611.3331597OpenAlexW2963962070WikidataQ130857394 ScholiaQ130857394MaRDI QIDQ5145214

Keren Censor-Hillel, Ami Paz, Michal Dory, Nir Bacrach, Yuval Efron, Dean Leitersdorf

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/1905.10284

zbMATH Keywords

optimization problemsdistributed computingapproximation algorithmscommunication complexitycongest

Mathematics Subject Classification ID

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

Related Items (8)

Why Extension-Based Proofs Fail ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ Simple and local independent set approximation ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed Spanner Approximation ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

This page was built for publication: Hardness of Distributed Optimization