2026-07-25T06:17:23Z https://drops.dagstuhl.de/oai

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

On the Approximation Ratio of the k-Opt and Lin-Kernighan Algorithm for Metric and Graph TSP Zhong, Xianghui traveling salesman problem metric TSP graph TSP k-Opt algorithm Lin-Kernighan algorithm approximation algorithm approximation ratio. The k-Opt and Lin-Kernighan algorithm are two of the most important local search approaches for the Metric TSP. Both start with an arbitrary tour and make local improvements in each step to get a shorter tour. We show that for any fixed k ≥ 3 the approximation ratio of the k-Opt algorithm for Metric TSP is O(√[k]{n}). Assuming the Erdős girth conjecture, we prove a matching lower bound of Ω(√[k]{n}). Unconditionally, we obtain matching bounds for k = 3,4,6 and a lower bound of Ω(n^{2/(3k-3)}). Our most general bounds depend on the values of a function from extremal graph theory and are tight up to a factor logarithmic in the number of vertices unconditionally. Moreover, all the upper bounds also apply to a parameterized version of the Lin-Kernighan algorithm with appropriate parameter. We also show that the approximation ratio of k-Opt for Graph TSP is Ω(log(n)/(log log(n))) and O({log(n)/(log log(n))}^{log₂(9)+ε}) for all ε > 0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xianghui Zhong 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.83 urn:nbn:de:0030-drops-129497 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.83 eng https://creativecommons.org/licenses/by/3.0/legalcode