# Faster Parallel Algorithm for Approximate Shortest Path

Preprint · Jason Li

- Archive id: arxiv:1911.01626
- Published: 2019-11-05
- arXiv: https://arxiv.org/abs/1911.01626
- Source URL: https://arxiv.org/abs/1911.01626
- PDF: https://arxiv.org/pdf/1911.01626
- Provenance: arxiv

## Abstract

We present the first $m\\,\\text{polylog}(n)$ work, $\\text{polylog}(n)$ time algorithm in the PRAM model that computes $(1+ε)$-approximate single-source shortest paths on weighted, undirected graphs. This improves upon the breakthrough result of Cohen~\[JACM'00\] that achieves $O(m^{1+ε\_0})$ work and $\\text{polylog}(n)$ time. While most previous approaches, including Cohen's, leveraged the power of hopsets, our algorithm builds upon the recent developments in \\emph{continuous optimization}, studying the shortest path problem from the lens of the closely-related \\emph{minimum transshipment} problem. To obtain our algorithm, we demonstrate a series of near-linear work, polylogarithmic-time reductions between the problems of approximate shortest path, approximate transshipment, and $\\ell\_1$-embeddings, and establish a recursive algorithm that cycles through the three problems and reduces the graph size on each cycle. As a consequence, we also obtain faster parallel algorithms for approximate transshipment and $\\ell\_1$-embeddings with polylogarithmic distortion. The minimum transshipment algorithm in particular improves upon the previous best $m^{1+o(1)}$ work sequential algorithm of Sherman~\[SODA'17\]. To improve readability, the paper is almost entirely self-contained, save for several staple theorems in algorithms and combinatorics.

_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.