Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Authors:
Preprint
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.
Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems2016
- Hollow Heaps2015
- Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back2013
- Superlinear Lower Bounds for Multipass Graph Processing2013
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time2009
- Streaming algorithm for graph spanners—single pass and constant processing time per edgeInformation Processing Letters, 2008
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphsRandom Structures & Algorithms, 2006
- On graph problems in a semi-streaming modelTheoretical Computer Science, 2005
- Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming modelsDistributed Computing, 2005
- Deterministic Constructions of Approximate Distance Oracles and Spanners2005