{"ID":2890127,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.19859","arxiv_id":"2507.19859","title":"Improved 2-Approximate Shortest Paths for close vertex pairs","abstract":"An influential result by Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2000) implies an algorithm that can compute approximate shortest paths for all vertex pairs in $\\tilde{O}(n^{2+O\\left(\\frac{1}{k}\\right )})$ time, ensuring that the output distance is at most twice the actual shortest path, provided the pairs are at least $k$ apart, where $k \\ge 2$. We present the first improvement on this result in over 25 years. Our algorithm achieves roughly same $\\tilde{O}(n^{2+\\frac{1}{k}})$ runtime but applies to vertex pairs merely $O(\\log k)$ apart, where $\\log k \\ge 1$. When $k=\\log n$, the running time of our algorithm is $\\tilde{O}(n^2)$ and it works for all pairs at least $O(\\log \\log n)$ apart. Our algorithm is combinatorial, randomized, and returns correct results for all pairs with a high probability.","short_abstract":"An influential result by Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2000) implies an algorithm that can compute approximate shortest paths for all vertex pairs in $\\tilde{O}(n^{2+O\\left(\\frac{1}{k}\\right )})$ time, ensuring that the output distance is at most twice the actual shortest path, provided the pairs are at l...","url_abs":"https://arxiv.org/abs/2507.19859","url_pdf":"https://arxiv.org/pdf/2507.19859v1","authors":"[\"Manoj Gupta\"]","published":"2025-07-26T08:24:09Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}