Near-optimal approximate shortest paths and transshipment in distributed and streaming models

DOI10.4230/LIPICS.DISC.2017.7MaRDI QIDQ6487479zbMATH OpenFDO

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

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2017.7

zbMATH Keywords

gradient descentshortest pathsshortest transshipmentspannerundirected min-cost flow

Mathematics Subject Classification ID

Distributed algorithms (68W15) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

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

Cited in

(11)

• Near-optimal clustering in the \(k\)-machine model
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• Distributed distance computation and routing with small messages
• A distributed algorithm for directed minimum-weight spanning tree
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Faster distributed shortest path approximations via shortcuts
• Large-scale distributed algorithms for facility location with outliers
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• Distributed distance approximation
• Distance computations in the hybrid network model via oracle simulations
• Constant-round spanners and shortest paths in congested clique and MPC

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 Q6487479)