2026-07-24T03:39:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16391 2024-03-06T10:57:21Z ddc:004 open_access

New Additive Approximations for Shortest Paths and Cycles Deng, Mingyang Kirkpatrick, Yael Rong, Victor Vassilevska Williams, Virginia Zhong, Ziqian Fine-grained Complexity Additive Approximation This paper considers additive approximation algorithms for All-Pairs Shortest Paths (APSP) and Shortest Cycle in undirected unweighted graphs. The results are as follows: - We obtain the first +2-approximation algorithm for APSP in n-vertex graphs that improves upon Dor, Halperin and Zwick’s (SICOMP'00) Õ(n^{7/3}) time algorithm. The new algorithm runs in Õ(n^2.29) time and is obtained via a reduction to Min-Plus product of bounded difference matrices. - We obtain the first additive approximation scheme for Shortest Cycle, generalizing the approximation algorithms of Itai and Rodeh (SICOMP'78) and Roditty and Vassilevska W. (SODA'12). For every integer r ≥ 0, we give an Õ(n+n^{2+r}/m^r) time algorithm that returns a +(2r+1)-approximate shortest cycle in any n-vertex, m-edge graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mingyang Deng and Yael Kirkpatrick and Victor Rong and Virginia Vassilevska Williams and Ziqian Zhong 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.50 urn:nbn:de:0030-drops-163919 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.50 eng https://creativecommons.org/licenses/by/4.0/legalcode