Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

We present a method for solving the transshipment problem---also known as uncapacitated minimum cost flow---up to a multiplicative error of $ 1 + \varepsilon $ in undirected graphs with nonnegative edge weights using a tailored gradient descent algorithm. Using $\widetilde{O}(\cdot)$ to hide polylogarithmic factors in $n$ (the number of nodes in the graph), our gradient descent algorithm takes $ \widetilde O(\varepsilon^{-2}) $ iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of $ \polylog n $. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a randomized rounding scheme, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve upon prior works by obtaining the following results: (1) Broadcast CONGEST model: $ (1 + \varepsilon) $-approximate SSSP using $ \widetilde{O} ((\sqrt{n} + D) \varepsilon^{-3}) $ rounds, where $ D $ is the (hop) diameter of the network. (2) Broadcast Congested Clique model: $ (1 + \varepsilon) $-approximate transshipment and SSSP using $ \widetilde{O} (\varepsilon^{-2}) $ rounds. (3) Multipass Streaming model: $ (1 + \varepsilon) $-approximate transshipment and SSSP using $ \widetilde{O} (n) $ space and $ \widetilde{O} (\varepsilon^{-2}) $ passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume nonnegative edge weights that are polynomially bounded in $n$; for general nonnegative weights, there is an additional multiplicative overhead equal to the logarithm of the maximum ratio between nonzero weights. Our algorithms can also handle asymmetric costs for traversing edges in opposite directions. In this case, we obtain an additional multiplicative dependence of the maximum ratio between the two costs on some edge.