# Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing

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

- Archive id: arxiv:2110.15944
- Published: 2021-10-29
- arXiv: https://arxiv.org/abs/2110.15944
- Source URL: https://arxiv.org/abs/2110.15944
- PDF: https://arxiv.org/pdf/2110.15944
- Provenance: arxiv

## Abstract

We provide universally-optimal distributed graph algorithms for $(1+\\varepsilon)$-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 \\cdot n^{o(1)}$ rounds whenever a $T$-round algorithm exists for $G$. This includes $D \\cdot n^{o(1)}$-round algorithms for any planar or excluded-minor network. Our algorithms never require more than $(\\sqrt{n} + D) \\cdot n^{o(1)}$ rounds, resulting in the first sub-linear-round distributed algorithm for transshipment. The key technical contribution leading to these results is the first efficient $n^{o(1)}$-competitive linear $\\ell\_1$-oblivious routing operator that does not require the use of $\\ell\_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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.