Fast approximate shortest paths in the congested clique
Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2021. Fast approximate shortest paths in the congested clique. Distributed Computing. 34, 463–487.
Download (ext.)
https://doi.org/10.1007/s00446-020-00380-5
[Published Version]
Journal Article
| Published
| English
Scopus indexed
Author
Censor-Hillel, Keren;
Dory, Michal;
Korhonen, JanneISTA;
Leitersdorf, Dean
Department
Abstract
We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include:
A (2+ϵ)-approximation for all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.
A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√) sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.
Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O~(n1/6) rounds.
Publishing Year
Date Published
2021-12-01
Journal Title
Distributed Computing
Publisher
Springer Nature
Acknowledgement
Open access funding provided by Institute of Science and Technology (IST Austria). We thank Mohsen Ghaffari, Michael Elkin and Merav Parter for fruitful discussions. This project has received funding from the European Union’s Horizon 2020 Research And Innovation Program under Grant Agreement No. 755839.
Volume
34
Page
463-487
ISSN
eISSN
IST-REx-ID
Cite this
Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest paths in the congested clique. Distributed Computing. 2021;34:463-487. doi:10.1007/s00446-020-00380-5
Censor-Hillel, K., Dory, M., Korhonen, J., & Leitersdorf, D. (2021). Fast approximate shortest paths in the congested clique. Distributed Computing. Springer Nature. https://doi.org/10.1007/s00446-020-00380-5
Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf. “Fast Approximate Shortest Paths in the Congested Clique.” Distributed Computing. Springer Nature, 2021. https://doi.org/10.1007/s00446-020-00380-5.
K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate shortest paths in the congested clique,” Distributed Computing, vol. 34. Springer Nature, pp. 463–487, 2021.
Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2021. Fast approximate shortest paths in the congested clique. Distributed Computing. 34, 463–487.
Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested Clique.” Distributed Computing, vol. 34, Springer Nature, 2021, pp. 463–87, doi:10.1007/s00446-020-00380-5.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Web of Science
View record in Web of Science®Sources
arXiv 1903.05956