Metraipolis › archive › dc_bdf89ee89073

Smallest Multiplicative Stretch for an $α$-APASP Below $\widetilde O \left(n^ω\right)$ Runtime — arXiv:2611.04736

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04736
License (as archived)
CC0-1.0
Archived
2026-11-04T19:07:34.428Z
SHA-256 of the archived text
9f9163e9fc57f07138c295681ef11c2aca9fe9cf00079fd7f4a75e163af7930d
Stable URL of this page
https://metraipolis.com/documento/dc_bdf89ee89073

How to cite

Smallest Multiplicative Stretch for an $α$-APASP Below $\widetilde O \left(n^ω\right)$ Runtime — arXiv:2611.04736 — arXiv (en), https://arxiv.org/abs/2611.04736 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bdf89ee89073 (Metraipolis archive dc_bdf89ee89073, sha256 9f9163e9fc57f07138c295681ef11c2aca9fe9cf00079fd7f4a75e163af7930d)
BibTeX
@misc{dcbdf89ee89073,
  title = {Smallest Multiplicative Stretch for an $α$-APASP Below $widetilde O left(n^ωright)$ Runtime — arXiv:2611.04736},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04736},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bdf89ee89073; sha256 9f9163e9fc57f07138c295681ef11c2aca9fe9cf00079fd7f4a75e163af7930d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04736. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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^{\omega+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 $\omega\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 $\omega\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^{\omega-\frac{(\omega-2)^2}{\omega-1}+o(1)}\log^{O(1)}W_{\max})$ runtime, with exponent below $\omega$ whenever $\omega>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})$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.04736 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:40:52.454Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).