On the Approximation Ratio of the k-Opt and Lin-Kernighan Algorithm for Metric TSP
share
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 is O(√(n)). Assuming the Erdős girth conjecture, we prove a matching lower bound of Ω(√(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 sharp up to a logarithmic factor unconditionally. Moreover, all the upper bounds also apply to a parameterized version of the Lin-Kernighan algorithm with appropriate parameter.
READ FULL TEXT