arXiv preprint ·
Smallest Multiplicative Stretch for an $α$-APASP Below $\widetilde O \left(n^ω\right)$ Runtime
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Dor, Halperin and Zwick [FOCS'96; SICOMP'00] showed that $(2-\varepsilon)$-APASP is at least as hard as BMM for every fixed $0<\varepsilon<1$. Zwick [FOCS'98; JACM'02] gave a $2$-APASP algorithm in $\widetilde O(n^{ω+o(1)}\log W_{\max})$ runtime, where $W_{\max}$ is the maximum edge weight. Bringmann, K{ü}nnemann and W{ę}grzycki [STOC'19] removed this logarithmic factor. Using OpenAI's recent bound $ω\leq\frac{9}{4}$ gives $\widetilde O\left(n^{\frac{9}{4}+o(1)}\right)$ time. We present two weighted undirected $2$-APASP algorithms. The first uses $(\min,\max)$-products. Earlier rectangular FMM bounds of Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'24] and Alman, Duan, Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'25] give $\widetilde O(n^{2.36999465})$ runtime, below the previous $ω\leq2.371177$ of Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog [arXiv'26]. Current rectangular FMM bounds give $\widetilde O(n^{2.34549151})$, independent of $W_{\max}$. For integer weights, our second algorithm has $\widetilde O(n^{ω-\frac{(ω-2)^2}{ω-1}+o(1)}\log^{O(1)}W_{\max})$ runtime, with exponent below $ω$ whenever $ω>2$. The rectangular bounds of Uzna{ń}ski [arXiv'26] or of Amanov, van den Berg and Zuiddam [arXiv'26] give $\widetilde O(n^{2.17157288}\log^{O(1)}W_{\max})$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Constant-Factor Approximation for Capacitated Facility Location with Outliers
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Semidirect sums of tensors and the matrix multiplication exponent
Sublinear Metric Distortion for Matching
Incremental Open Addressing Has No Time-Space Tradeoff
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.