# Improved All-Pairs Approximate Shortest Paths in Congested Clique

Preprint · Hong Duc Bui, Shashwat Chandra, Yi-Jun Chang, Michal Dory, Dean Leitersdorf

- Archive id: arxiv:2405.02695
- Published: 2024-05-04
- arXiv: https://arxiv.org/abs/2405.02695
- Source URL: https://arxiv.org/abs/2405.02695
- PDF: https://arxiv.org/pdf/2405.02695
- Provenance: arxiv

## Abstract

In this paper, we present a new randomized $O(1)$-approximation algorithm for the All-Pairs Shortest Paths (APSP) problem in weighted undirected graphs that runs in just $O(\\log \\log \\log n)$ rounds in the Congested-Clique model. Before our work, the fastest algorithms achieving an $O(1)$-approximation for APSP in weighted undirected graphs required $\\operatorname{poly}(\\log n)$ rounds, as shown by Censor-Hillel, Dory, Korhonen, and Leitersdorf (PODC 2019 & Distributed Computing 2021). In the unweighted undirected setting, Dory and Parter (PODC 2020 & Journal of the ACM 2022) obtained $O(1)$-approximation in $\\operatorname{poly}(\\log \\log n)$ rounds. By terminating our algorithm early, for any given parameter $t \\geq 1$, we obtain an $O(t)$-round algorithm that guarantees an $O\\left(\\log^{1/2^t} n\\right)$ approximation in weighted undirected graphs. This tradeoff between round complexity and approximation factor offers flexibility, allowing the algorithm to adapt to different requirements. In particular, for any constant $\\varepsilon \> 0$, an $O\\left(\\log^\\varepsilon n\\right)$-approximation can be obtained in $O(1)$ rounds. Previously, $O(1)$-round algorithms were only known for $O(\\log n)$-approximation, as shown by Chechik and Zhang (PODC 2022). A key ingredient in our algorithm is a lemma that, under certain conditions, allows us to improve an $a$-approximation for APSP to an $O(\\sqrt{a})$-approximation in $O(1)$ rounds. To prove this lemma, we develop several new techniques, including an $O(1)$-round algorithm for computing the $k$-nearest nodes, as well as new types of hopsets and skeleton graphs based on the notion of $k$-nearest nodes.

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