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.
@InProceedings{zhong:LIPIcs.ESA.2020.83, author = {Zhong, Xianghui}, title = {{On the Approximation Ratio of the k-Opt and Lin-Kernighan Algorithm for Metric and Graph TSP}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {83:1--83:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.83}, URN = {urn:nbn:de:0030-drops-129497}, doi = {10.4230/LIPIcs.ESA.2020.83}, annote = {Keywords: traveling salesman problem, metric TSP, graph TSP, k-Opt algorithm, Lin-Kernighan algorithm, approximation algorithm, approximation ratio.} }
Feedback for Dagstuhl Publishing