Fast approximate shortest paths in the congested clique

K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, in:, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin, ACM, 2019, pp. 74–83.


Conference Paper | Published | English
Author
; ; ;
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 problem in O(log²n / ε) 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 problem from O(√n) sources in O(log² n / ε) 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 Õ(n^{1/6}) rounds.
Publishing Year
Date Published
2019-08-01
Proceedings Title
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin
Page
74-83
Conference
PODC: Symposium on Principles of Distributed Computing
Conference Location
Toronto, ON, Canada
Conference Date
2019-07-29 – 2019-08-02
IST-REx-ID

Cite this

Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest paths in the congested clique. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin. ACM; 2019:74-83. doi:10.1145/3293611.3331633
Censor-Hillel, K., Dory, M., Korhonen, J., & Leitersdorf, D. (2019). Fast approximate shortest paths in the congested clique. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin (pp. 74–83). Toronto, ON, Canada: ACM. https://doi.org/10.1145/3293611.3331633
Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf. “Fast Approximate Shortest Paths in the Congested Clique.” In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin, 74–83. ACM, 2019. https://doi.org/10.1145/3293611.3331633.
K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate shortest paths in the congested clique,” in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin, Toronto, ON, Canada, 2019, pp. 74–83.
Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2019. Fast approximate shortest paths in the congested clique. Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin. PODC: Symposium on Principles of Distributed Computing 74–83.
Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested Clique.” Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin, ACM, 2019, pp. 74–83, doi:10.1145/3293611.3331633.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1903.05956

Search this title in

Google Scholar
ISBN Search