Lune

SODA2022Top-tier venue

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based ℓ1-Oblivious Routing

Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, Xiaorui Sun

Abstract

We provide universally-optimal distributed graph algorithms for (1+∊)-approximate shortest path problems including shortest-path-tree and transshipment. The universal optimality of our algorithms guarantees that, on any n-node network G, our algorithm completes in T · no(1) rounds whenever a T-round algorithm exists for G. This includes D · no(1)-round algorithms for any planar or excluded-minor network. Our algorithms never require more than rounds, resulting in the first sub-linear-round distributed algorithm for transshipment. The key technical contribution leading to these results is the first efficient no(1)-competitive linear ℓ1-oblivious routing operator that does not require the use of ℓ1-embeddings. Our construction is simple, solely based on low-diameter decompositions, and—in contrast to all known constructions—directly produces an oblivious flow instead of just an approximation of the optimal flow cost. This also has the benefit of simplifying the interaction with Sherman's multiplicative weight framework [SODA'17] in the distributed setting and its subsequent rounding procedures.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Minor Sparsifiers and the Distributed Laplacian Paradigm cites Parallel approximate undirected shortest paths via low hop emulators
  • Minor Sparsifiers and the Distributed Laplacian Paradigm cites Faster parallel algorithm for approximate shortest path
  • Faster parallel algorithm for approximate shortest path cites Parallel approximate undirected shortest paths via low hop emulators
  • Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ₁-Oblivious Routings cites Parallel approximate undirected shortest paths via low hop emulators
  • Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ₁-Oblivious Routings cites Faster parallel algorithm for approximate shortest path
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Universal Optimality of Dijkstra Via Beyond-Worst-Case HeapsBernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan et al.FOCS 2024 · 33 citations
  2. Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ₁-Oblivious RoutingsRasmus Kyng, Maximilian Probst Gutenberg, Tim RiederFOCS 2025 · 1 citation

Builds on6

  1. Parallel approximate undirected shortest paths via low hop emulatorsAlexandr Andoni, Clifford Stein, Peilin ZhongSTOC 2020 · 50 citations
  2. Faster parallel algorithm for approximate shortest pathJason LiSTOC 2020 · 48 citations
  3. Hop-constrained oblivious routingMohsen Ghaffari, Bernhard Haeupler, Goran ZuzicSTOC 2021 · 15 citations
  4. Minor Sparsifiers and the Distributed Laplacian ParadigmSebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng et al.FOCS 2021 · 12 citations
  5. Network Coding Gaps for Completion Times of Multiple UnicastsBernhard Haeupler, David Wajc, Goran ZuzicFOCS 2020 · 12 citations

Related papers

  1. Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithmsVáclav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic et al.STOC 2022 · 22 citations
  2. Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear TimeAaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol SaranurakFOCS 2021 · 27 citations
  3. Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel ApplicationsVáclav Rozhon, Michael Elkin, Christoph Grunau, Bernhard HaeuplerFOCS 2022 · 5 citations
  4. New hardness results for planar graph problems in p and an algorithm for sparsest cutAmir Abboud, Vincent Cohen-Addad, Philip N. KleinSTOC 2020 · 6 citations
  5. Universally-optimal distributed algorithms for known topologiesBernhard Haeupler, David Wajc, Goran ZuzicSTOC 2021
Dusk over the sea between two cliffs drawn in fine vertical lines