On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm

Abstract

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\ge 3$ the approximation ratio of the $k$-Opt algorithm for Metric TSP is $O(\sqrt[k]{n})$. Assuming the Erdős girth conjecture, we prove a matching lower bound of $\Omega (\sqrt[k]{n})$. Unconditionally, we obtain matching bounds for $k=3,4,6$ and a lower bound of $\Omega (n^{\frac{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 generalization of the Lin-Kernighan algorithm with appropriate parameters. We also show that the approximation ratio of $k$-Opt for Graph TSP is $\Omega \left(\frac{\log (n)}{\log \log (n)}\right)$ and $O\left({\left(\frac{\log (n)}{\log \log (n)}\right)}^{{\log }_2(9)+\epsilon }\right)$ for all $\epsilon >0$. For the (1,2)-TSP we give a lower bound of $\frac{11}{10}$ on the approximation ratio of the $k$-improv and $k$-Opt algorithm for arbitrary fixed $k$.

References in corpus (1)

• The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem

Cited by in corpus (2)

• The Approximation Ratio of the $k$-Opt Heuristic for the Euclidean Traveling Salesman Problem
• On the Approximation Ratio of the 3-Opt Algorithm for the (1,2)-TSP