Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Authors:
- Ruben BeckerRBRuben Becker
- Sebastian ForsterSFSebastian Forster
- Andreas KarrenbauerAKAndreas Karrenbauer
- Christoph LenzenCLChristoph Lenzen
- 1 January 2021
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 50 (3) , 815-856
Abstract
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.
Keywords
All Related Versions
This publication has 48 references indexed in Scilit:
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spannersACM Transactions on Algorithms, 2011
- 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
- Δ-stepping: a parallelizable shortest path algorithmJournal of Algorithms, 2003
- Polylog-time and near-linear work approximation scheme for undirected shortest pathsJournal of the ACM, 2000
- Time–Work Tradeoffs of the Single-Source Shortest Paths ProblemJournal of Algorithms, 1999
- A Randomized Parallel Algorithm for Single-Source Shortest PathsJournal of Algorithms, 1997
- Time-work tradeoffs for parallel algorithmsJournal of the ACM, 1997
- Using Selective Path-Doubling for Parallel Shortest-Path ComputationsJournal of Algorithms, 1997
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987