2026-08-13T19:29:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20162 2024-07-02T07:52:49Z ddc:004 open_access

Sublinear Algorithms for TSP via Path Covers Behnezhad, Soheil Roghani, Mohammad Rubinstein, Aviad Saberi, Amin Sublinear Algorithms Traveling Salesman Problem Approximation Algorithm (1 2)-TSP Graphic TSP We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related maximum path cover problem, which asks for a collection of vertex disjoint paths that include the maximum number of edges. We show that for any fixed ε > 0, there is an algorithm that (1/2 - ε)-approximates the maximum path cover size of an n-vertex graph in Õ(n) time. This improves upon a (3/8-ε)-approximate Õ(n √n)-time algorithm of Chen, Kannan, and Khanna [ICALP'20]. Equipped with our path cover algorithm, we give an Õ(n) time algorithm that estimates the cost of (1,2)-TSP within a factor of (1.5+ε) which is an improvement over a folklore (1.75 + ε)-approximate Õ(n)-time algorithm, as well as a (1.625+ε)-approximate Õ(n√n)-time algorithm of [CHK ICALP'20]. For graphic TSP, we present an Õ(n) algorithm that estimates the cost of graphic TSP within a factor of 1.83 which is an improvement over a 1.92-approximate Õ(n) time algorithm due to [CHK ICALP'20, Behnezhad FOCS'21]. We show that the approximation can be further improved to 1.66 using n^{2-Ω(1)} time. All of our Õ(n) time algorithms are information-theoretically time-optimal up to polylog n factors. Additionally, we show that our approximation guarantees for path cover and (1,2)-TSP hit a natural barrier: We show better approximations require better sublinear time algorithms for the well-studied maximum matching problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Soheil Behnezhad and Mohammad Roghani and Aviad Rubinstein and Amin Saberi 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.19 urn:nbn:de:0030-drops-201623 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.19 eng https://creativecommons.org/licenses/by/4.0/legalcode