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

DOI10.4230/LIPICS.ESA.2020.83MaRDI QIDQ6326125arXivFDO

Authors Xianghui Zhong

Publication date 27 September 2019

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2020.83

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

arXiv classification

cs.DMcs.DSmath.CO

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 $kgeq3$ the approximation ratio of the $k$-Opt algorithm for Metric TSP is $O(sqrt[k]n)$. Assuming the ErdH{o}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^{frac23k-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 parameters. We also show that the approximation ratio of $k$-Opt for Graph TSP is $Omegaleft(fraclog(n)loglog(n)ight)$ and $Oleft(left(fraclog(n)loglog(n)ight{)}^{lo{g}_2(9)+epsilon}ight)$ for all $epsilon>0$. For the (1,2)-TSP we give a lower bound of $frac1110$ on the approximation ratio of the $k$-improv and $k$-Opt algorithm for arbitrary fixed $k$.

This page was built for publication: On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326125)