Distributed Approximation Algorithms for Weighted Shortest Paths

Abstract

A distributed network is modeled by a graph having $n$ nodes (processors) and diameter $D$. We study the time complexity of approximating {\em weighted} (undirected) shortest paths on distributed networks with a $O(\log n)$ {\em bandwidth restriction} on edges (the standard synchronous \congest model). The question whether approximation algorithms help speed up the shortest paths (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted case of this problem is well-understood while its weighted counterpart is fundamental problem in the area of distributed approximation algorithms and remains widely open. We present new algorithms for computing both single-source shortest paths (\sssp) and all-pairs shortest paths (\apsp) in the weighted case. Our main result is an algorithm for \sssp. Previous results are the classic $O(n)$-time Bellman-Ford algorithm and an $\tilde{O}(n^{1/2+1/2k}+D)$-time $(8k\lceil \log (k+1)\rceil -1)$-approximation algorithm, for any integer $k\ge 1$, which follows from the result of Lenzen and Patt-Shamir (STOC 2013). (Note that Lenzen and Patt-Shamir in fact solve a harder problem, and we use $\tilde{O}(\cdot )$ to hide the $O(\poly\log n)$ term.) We present an $\tilde{O}(n^{1/2}{D}^{1/4}+D)$-time $(1+o(1))$-approximation algorithm for \sssp. This algorithm is {\em sublinear-time} as long as $D$ is sublinear, thus yielding a sublinear-time algorithm with almost optimal solution. When $D$ is small, our running time matches the lower bound of $\tilde{\Omega }(n^{1/2}+D)$ by Das Sarma et al. (SICOMP 2012), which holds even when $D=\Theta (\log n)$, up to a $\poly\log n$ factor.

Full version of STOC 2014

Cited by in corpus (13)

• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Distributed Algorithms for Directed Betweenness Centrality and All Pairs Shortest Paths
• Fast Partial Distance Estimation and Applications
• Distributed Subgraph Detection
• Minor Sparsifiers and the Distributed Laplacian Paradigm
• A Fast Network-Decomposition Algorithm and its Applications to Constant-Time Distributed Computation
• Super-fast MST Algorithms in the Congested Clique using $o(m)$ Messages
• Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set
• A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in $\tilde{O}(n^{3/2})$ Rounds
• On Efficient Distributed Construction of Near Optimal Routing Schemes
• A Distributed Enumeration Algorithm and Applications to All Pairs Shortest Paths, Diameter
• Fast Distributed Algorithms for Connectivity and MST in Large Graphs