Smallest Multiplicative Stretch for an $α$-APASP Below O (n^ω) Runtime

Dor, Halperin and Zwick [FOCS'96; SICOMP'00] showed that (2-ε)-APASP is at least as hard as BMM for every fixed 0<ε<1. Zwick [FOCS'98; JACM'02] gave a $2$-APASP algorithm in O(nω+o(1)log Wₘₐₓ) runtime, where Wₘₐₓ is the maximum edge weight. Bringmann, K{ü}nnemann and W{ę}grzycki [STOC'19] removed this logarithmic factor. Using OpenAI's recent bound ω≤9/4 gives O(n9/4+o(1)) 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 O(n2.36999465) runtime, below the previous ω≤2.371177 of Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog [arXiv'26]. Current rectangular FMM bounds give O(n2.34549151), independent of Wₘₐₓ. For integer weights, our second algorithm has O(nω-(ω-2)²/ω-1+o(1)logO(1)Wₘₐₓ) 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 O(n2.17157288logO(1)Wₘₐₓ).