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

Authors:

Abstract
We present a method for solving the shortest transshipmen} problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of $ 1 + \epsilon $ in undirected graphs with polynomially bounded integer edge weights using a tailored gradient descent algorithm. An important special case of the transshipment problem is the single-source shortest paths (SSSP) problem. Our gradient descent algorithm takes $ \epsilon^{-3} polylog{n} $ iterations, and in each iteration it needs to solve the transshipment problem up to a multiplicative error of $ polylog n $, where $ n $ is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. As a consequence, we improve prior work by obtaining the following results: (1) Broadcast congest model: $ (1 + \epsilon) $-approximate SSSP using $ \tilde{O} (\epsilon^{-O(1)}(\sqrt{n} + D)) $ rounds, where $ D $ is the (hop) diameter of the network. (2) Broadcast congested clique model: $ (1 + \epsilon) $-approximate transshipment and SSSP using $ \tilde{O} (\epsilon^{-O(1)}) $ rounds. (3) Multipass streaming model: $ (1 + \epsilon) $-approximate transshipment and SSSP using $ \tilde{O} (n) $ space and $ \tilde{O} (\epsilon^{-O(1)}) $ passes. The previously fastest 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 non-negative integer edge weights that are polynomially bounded in $ n $; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs, running times scale with the maximum ratio between the costs of both directions over all edges.