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

DOI10.1137/19M1286955MaRDI QIDQ4989920zbMATH OpenFDO

Authors Ruben Becker, Sebastian Forster, Andreas Karrenbauer, Christoph Lenzen

Publication date 27 May 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.05127

zbMATH Keywords

distributed algorithmsgradient descentshortest pathsstreaming algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Programming involving graphs or networks (90C35)

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 non-negative edge weights using a tailored gradient descent algorithm. Using $ildeO(cdot)$ to hide polylogarithmic factors in $n$ (the number of nodes in the graph), our gradient descent algorithm takes $ildeO(varepsilo{n}^{-2})$ iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of $operatornamepolylogn$. 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 work by obtaining the following results: (1) Broadcast CONGEST model: $(1+varepsilon)$-approximate SSSP using $ildeO((sqrtn+D)varepsilo{n}^{-3})$ rounds, where $D$ is the (hop) diameter of the network. (2) Broadcast congested clique model: $(1+varepsilon)$-approximate transshipment and SSSP using $ildeO(varepsilo{n}^{-2})$ rounds. (3) Multipass streaming model: $(1+varepsilon)$-approximate transshipment and SSSP using $ildeO(n)$ space and $ildeO(varepsilo{n}^{-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 non-negative 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.

Recommendations

• Near-optimal approximate shortest paths and transshipment in distributed and streaming models
• Faster distributed shortest path approximations via shortcuts
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Distributed approximation algorithms for weighted shortest paths
• Optimal distributed all pairs shortest paths and applications
• Partially dynamic efficient algorithms for distributed shortest paths
• Improved distributed algorithms for exact shortest paths

Cites work

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A hierarchy of lower bounds for sublinear additive spanners
• A parallel priority queue with constant time operations
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Automata, Languages and Programming
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Distributed approximation algorithms for weighted shortest paths
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification and hardness of distributed approximation
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Fast Approximate Shortest Paths in the Congested Clique
• Fast routing table construction using small messages (extended abstract)
• Fibonacci heaps and their uses in improved network optimization algorithms
• Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
• Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
• Generalized preconditioning and undirected minimum-cost flow
• Graph Distances in the Data-Stream Model
• Hollow heaps
• Hopsets with constant hopbound, and applications to approximate shortest paths
• scientific article; zbMATH DE number 5485557 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• Improved distributed algorithms for exact shortest paths
• Lower-Stretch Spanning Trees
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
• Network flows. Theory, algorithms, and applications.
• On a routing problem
• On graph problems in a semi-streaming model
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Scaling Algorithms for the Shortest Paths Problem
• Streaming algorithm for graph spanners-single pass and constant processing time per edge
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• Superlinear lower bounds for multipass graph processing
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Thorup-Zwick emulators are universally optimal hopsets
• Time-work tradeoffs for parallel algorithms
• Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
• Undirected single-source shortest paths with positive integer weights in linear time
• Using Selective Path-Doubling for Parallel Shortest-Path Computations
• Δ-stepping: a parallelizable shortest path algorithm

Cited in

(14)

• Fast approximate shortest paths in the congested clique
• Approximate minimum directed spanning trees under congestion
• Single-source shortest paths in the CONGEST model with improved bounds
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Minimum cost flow in the CONGEST model
• Online Spanners in Metric Spaces
• Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
• Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
• Near-optimal approximate shortest paths and transshipment in distributed and streaming models
• Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
• Online spanners in metric spaces
• A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs
• Almost optimal superconstant-pass streaming lower bounds for reachability

This page was built for publication: Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989920)