The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem

Abstract

Previous article Next article The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman ProblemChristos H. PapadimitriouChristos H. Papadimitriouhttps://doi.org/10.1137/0221030PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractIt is shown that finding a local optimum solution with respect to the Lin–Kernighan heuristic for the traveling salesman problem is PLS-complete, and thus as hard as any local search problem.[1] J. L. Bentley, Invited Talk at the First SIAM Symposium on Discrete Algorithms, 1990 Google Scholar[2] Michael R. Garey and , David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979x+338, A Guide to the Theory of NP-completeness 80g:68056 0411.68039 Google Scholar[3] J. J. Hopfield, Neural networks and physical systems with emergent collective computational abilities, Proc. Nat. Acad. Sci. U.S.A., 79 (1982), 2554–2558 83g:92024 CrossrefISIGoogle Scholar[4] D. S. Johnson, , C. H. Papadimitriou and , M. Yannakakis, How easy is local search?, Proceedings of Foundations of Computer Science, 1985, also in J. CSS. 37 (1988), pp. 79–100 Google Scholar[5] B. W. Kernighan and , S. Lin, An efficient heuristic procedure for partitioning graphs, Bell S. T. J., 49 (1970), 291–307 0333.05001 CrossrefGoogle Scholar[6] M. W. Krentel, On Finding Locally Optimal Solutions, Proceedings of the 4th Structures Conference, 1989 Google Scholar[7] M. W. Krentel, 1989, manuscript Google Scholar[8] S. Lin and , B. W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem, Operations Res., 21 (1973), 498–516 50:12194 0256.90038 CrossrefISIGoogle Scholar[9] G. Lueker, 1975, manuscript, Princeton University, Princeton, NJ Google Scholar[10] N. Megiddo and , C. H. Papadimitriou, On total functions, existence theorems and computational complexity, Theoret. Comput. Sci., 81 (1981), 317–324 10.1016/0304-3975(91)90200-L CrossrefISIGoogle Scholar[11] C. H. Papadimitriou, On graph-theoretic lemmata and complexity classes, Proceedings on Foundations of Computer Science, 1990 Google Scholar[12] Christos H. Papadimitriou and , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall Inc., Englewood Cliffs, N.J., 1982xvi+496 84k:90036 0503.90060 Google Scholar[13] C. H. Papadimitriou, , A. A. Schäffer and , M. Yannakakis, On the complexity of local search, Proc. STOC Conference, 1990 Google Scholar[14] Alejandro A. Schäffer and , Mihalis Yannakakis, Simple local search problems that are hard to solve, SIAM J. Comput., 20 (1991), 56–87 10.1137/0220004 91k:68065 0716.68048 LinkISIGoogle ScholarKeywordslocal searchtraveling salesman problemPLS-complete Previous article Next article FiguresRelatedReferencesCited ByDetails A discrete cuckoo search algorithm for traveling salesman problem and its application in cutting path optimizationComputers & Industrial Engineering, Vol. 169 | 1 Jul 2022 Cross Ref The complexity of gradient descent: CLS = PPAD ∩ PLSProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 15 June 2021 Cross Ref Exploring Large and Complex Environments Fast and Efficiently2021 IEEE International Conference on Robotics and Automation (ICRA) | 30 May 2021 Cross Ref Studying Heuristics Adaptation to a Specific Degree of Fuzziness2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE) | 1 Jul 2020 Cross Ref Hierarchical Coverage Path Planning in Complex 3D Environments2020 IEEE International Conference on Robotics and Automation (ICRA) | 1 May 2020 Cross Ref Computational Aspects of the Colorful Carathéodory TheoremDiscrete & Computational Geometry, Vol. 60, No. 3 | 14 March 2018 Cross Ref PPP-Completeness with Connections to Cryptography2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) | 1 Oct 2018 Cross Ref Das Traveling-Salesman-ProblemKombinatorische Optimierung | 25 July 2018 Cross Ref The Traveling Salesman ProblemCombinatorial Opt