On the Approximation Ratio of the k-Opt and Lin-Kernighan Algorithm for Metric and Graph TSP
Xianghui Zhong · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2020
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.