{"ID":2874775,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.04640","arxiv_id":"2509.04640","title":"Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms","abstract":"We present a $+2\\sum_{i=1}^{k+1}{W_i}$-APASP algorithm for dense weighted graphs with runtime $\\tilde O\\left(n^{2+\\frac{1}{3k+2}}\\right)$, where $W_{i}$ is the weight of an $i^{th}$ heaviest edge on a shortest path. Dor, Halperin and Zwick [FOCS'96, SICOMP'00] had two algorithms for the commensurate unweighted $+2\\cdot\\left( k+1\\right)$-APASP: $\\tilde O\\left(n^{2-\\frac{1}{k+2}}m^{\\frac{1}{k+2}}\\right)$ runtime for sparse graphs and $\\tilde O\\left(n^{2+\\frac{1}{3k+2}}\\right)$ runtime for dense graphs. Cohen and Zwick [SODA'97, JALG'01] adapted the sparse variant to weighted graphs: $+2\\sum_{i=1}^{k+1}{W_i}$-APASP algorithm in the same runtime. We show an algorithm for dense weighted graphs. For nearly additive APASP, we present a $\\left(1+\\varepsilon,\\min{\\left\\{2W_1,4W_{2}\\right\\}}\\right)$-APASP algorithm with $\\tilde O\\left(\\left(\\frac{1}{\\varepsilon}\\right)^{O\\left(1\\right)}\\cdot n^{2.15135313}\\cdot\\log W\\right)$ runtime. This improves the $\\left(1+\\varepsilon,2W_1\\right)$-APASP of Saha and Ye [SODA'24]. For multiplicative APASP, we show a framework of $\\left(\\frac{3\\ell +4}{\\ell + 2}+\\varepsilon\\right)$-APASP algorithms, reducing the runtime of Akav and Roditty [ESA'21] for dense graphs and generalizing the $\\left(2+\\varepsilon\\right)$-APASP algorithm of Dory et al [SODA'24]. Our base case is a $\\left(\\frac{7}{3}+\\varepsilon\\right)$-APASP in $\\tilde O\\left(\\left(\\frac{1}{\\varepsilon}\\right)^{O\\left(1\\right)}\\cdot n^{2.15135313}\\cdot \\log W\\right)$ runtime, improving the $\\frac{7}{3}$-APASP algorithm of Baswana and Kavitha [FOCS'06, SICOMP'10] for dense graphs. Finally, we \"bypass\" an $\\tilde Ω\\left(n^ω\\right)$ conditional lower bound by Dor, Halperin, and Zwick for $α$-APASP with $α\u003c 2$, by allowing an additive term (e.g. $\\left(\\frac{6k+3}{3k+2},\\sum_{i=1}^{k+1}W_{i}\\right)$-APASP in $\\tilde O\\left(n^{2+\\frac{1}{3k+2}}\\right)$ runtime).","short_abstract":"We present a $+2\\sum_{i=1}^{k+1}{W_i}$-APASP algorithm for dense weighted graphs with runtime $\\tilde O\\left(n^{2+\\frac{1}{3k+2}}\\right)$, where $W_{i}$ is the weight of an $i^{th}$ heaviest edge on a shortest path. Dor, Halperin and Zwick [FOCS'96, SICOMP'00] had two algorithms for the commensurate unweighted $+2\\cdot...","url_abs":"https://arxiv.org/abs/2509.04640","url_pdf":"https://arxiv.org/pdf/2509.04640v2","authors":"[\"Liam Roditty\",\"Ariel Sapir\"]","published":"2025-09-04T20:00:17Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}