2026-07-22T12:14:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9013 2024-03-06T10:43:09Z ddc:004 open_access

New Approximation Algorithms for (1,2)-TSP Adamaszek, Anna Mnich, Matthias Paluch, Katarzyna Approximation algorithms traveling salesperson problem cycle cover We give faster and simpler approximation algorithms for the (1,2)-TSP problem, a well-studied variant of the traveling salesperson problem where all distances between cities are either 1 or 2. Our main results are two approximation algorithms for (1,2)-TSP, one with approximation factor 8/7 and run time O(n^3) and the other having an approximation guarantee of 7/6 and run time O(n^{2.5}). The 8/7-approximation matches the best known approximation factor for (1,2)-TSP, due to Berman and Karpinski (SODA 2006), but considerably improves the previous best run time of O(n^9). Thus, ours is the first improvement for the (1,2)-TSP problem in more than 10 years. The algorithm is based on combining three copies of a minimum-cost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using "half-edges". The resulting multigraph is then edge-colored with four colors so that each color class yields a collection of vertex-disjoint paths. The paths from one color class can then be extended to an 8/7-approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best 8/7-approximation. The 7/6-approximation algorithm is similar and even simpler, and has the advantage of not using Hartvigsen's complicated algorithm for computing a minimum-cost triangle-free cycle cover. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Adamaszek and Matthias Mnich and Katarzyna Paluch 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.9 urn:nbn:de:0030-drops-90133 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.9 eng https://creativecommons.org/licenses/by/3.0/legalcode