Distributed Approximation Algorithms for Weighted Shortest Paths

Abstract:
In this talk, I will present a distributed algorithm for computing single-source shortest paths (SSSP) and related problems in the standard distributed CONGEST model. Let n be the number of nodes in the network, D be its diameter, and $\tilde O()$ hide the $O(\poly\log n)$ term. Previous results are the classic $\tilde O(n)$-time Bellman-Ford algorithm and a $\tilde O(n^{1/2+1/2k}+D)$-time $(8k\lceil \log (k+1) \rceil -1)$-approximation algorithm, for any integer $k\geq 1$, by Lenzen and Patt-Shamir (STOC 2013). I will present a $\tilde O(n^{1/2}D^{1/4}+D)$-time $(1+o(1))$-approximation algorithm for this problem. The running time of this algorithm almost matches the lower bound of $\tilde \Omega(n^{1/2}+D)$ by Das Sarma et al. (STOC 2011) which holds even when $D=\Theta(\log n)$. If time permits, I will also present algorithms for all-pairs shortest paths (APSP) and an $\tilde O(n^{1/2})$ time algorithm on fully-connected networks, which guarantees an exact solution for SSSP and a $(2+o(1))$-approximate solution for APSP.

All our algorithms rely on two new simple tools: {\em light-weight algorithm for bounded-hop \sssp} and {\em shortest-path diameter reduction via shortcuts}. These tools might be of an independent interest and useful in designing algorithms in other settings.

This talk is based on a paper to appear in STOC 2014.