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

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 Optimization | 14 March 2018 Cross Ref Determination of the Optimal Routes for Autonomous Unmanned Aerial Vehicle Under Varying Wind with Using of the Traveling Salesman Problem AlgorithmComputer Information Systems and Industrial Management | 9 September 2016 Cross Ref General BibliographyParadigms of Combinatorial Optimization | 8 August 2014 Cross Ref Local Search: Complexity and ApproximationParadigms of Combinatorial Optimization | 8 August 2014 Cross Ref Survey of Methodologies for TSP and VRPModels for Practical Routing Problems in Logistics | 20 February 2014 Cross Ref Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSPAlgorithmica, Vol. 68, No. 1 | 19 June 2013 Cross Ref Local Search: Complexity and ApproximationParadigms of Combinatorial Optimization | 13 February 2013 Cross Ref A Hard Problem: The TSPGraphs, Networks and Algorithms | 1 Jan 2013 Cross Ref The Traveling Salesman ProblemCombinatorial Optimization | 27 October 2011 Cross Ref Improving Lin-Kernighan-Helsgaun with Crossover on Clustered Instances of the TSPParallel Problem Solving from Nature - PPSN XII | 1 Jan 2012 Cross Ref Das Traveling-Salesman-ProblemKombinatorische Optimierung | 4 May 2012 Cross Ref Il problema del commesso viaggiatoreOttimizzazione Combinatoria | 1 Jan 2011 Cross Ref Le probléme du voyageur de commerceOptimisation combinatoire | 1 Jan 2010 Cross Ref Local Search: Simple, Successful, But Sometimes SluggishAutomata, Languages and Programming | 1 Jan 2010 Cross Ref A glimpse at Christos H. PapadimitriouComputer Science Review, Vol. 3, No. 2 | 1 May 2009 Cross Ref MultiProcessor Scheduling is PLS-Complete2009 42nd Hawaii International Conference on System Sciences | 1 Jan 2009 Cross Ref Computational bounds for local search in combinatorial optimizationComputational Mathematics and Mathematical Physics, Vol. 48, No. 5 | 21 May 2008 Cross Ref Memetic Algorithms: The Polynomial Local Search Complexity Theory PerspectiveJournal of Mathematical Modelling and Algorithms, Vol. 7, No. 1 | 12 October 2007 Cross Ref The NP-completeness columnACM Transactions on Algorithms, Vol. 3, No. 2 | 1 May 2007 Cross Ref A Computational Approach to TSP Performance Prediction Using Data Mining21st International Conference on Advanced Information Networking and Applications Workshops (AINAW'07) | 1 Jan 2007 Cross Ref Evolving Combinatorial Problem Instances That Are Difficult to SolveEvolutionary Computation, Vol. 14, No. 4 | 1 Dec 2006 Cross Ref A Survey of Approximation Results for Local Search AlgorithmsEfficient Approximation and Online Algorithms | 1 Jan 2006 Cross Ref Property Analysis of Symmetric Travelling Salesman Problem Instances Acquired Through EvolutionEvolutionary Computation in Combinatorial Optimization | 1 Jan 2005 Cross Ref BIBLIOGRAPHYStochastic Local Search | 1 Jan 2005 Cross Ref Approximate Local Search in Combinatorial OptimizationJames B. Orlin, Abraham P. Punnen, and Andreas S. SchulzSIAM Journal on Computing, Vol. 33, No. 5 | 17 February 2012AbstractPDF (179 KB)A survey of very large-scale neighborhood search techniquesDiscrete Applied Mathematics, Vol. 123, No. 1-3 | 1 Nov 2002 Cross Ref The Traveling Salesman ProblemCombinatorial Optimization | 1 Jan 2002 Cross Ref Solving the Traveling Salesman Problem Using the Enhanced Genetic AlgorithmAdvances in Artificial Intelligence | 16 May 2001 Cross Ref A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the PlaneAlgorithms and Computation | 29 January 2002 Cross Ref The Traveling Salesman ProblemCombinatorial Optimization | 1 Jan 2000 Cross Ref Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, Vol. 45, No. 5 | 1 Sep 1998 Cross Ref Probabilistic analysis of 2-opt for travelling salesman problemsInternational Journal of Systems Science, Vol. 29, No. 3 | 1 Mar 1998 Cross Ref Finding optimal subgraphs by local searchTheoretical Computer Science, Vol. 172, No. 1-2 | 1 Feb 1997 Cross Ref Metaheuristics: A bibliographyAnnals of Operations Research, Vol. 63, No. 5 | 1 Oct 1996 Cross Ref The complexity of searching implicit graphsArtificial Intelligence, Vol. 86, No. 1 | 1 Sep 1996 Cross Ref Routing problems: A bibliographyAnnals of Operations Research, Vol. 61, No. 1 | 1 Dec 1995 Cross Ref Integer Linear Programs and Local Search for Max-CutSvatopluk PoljakSIAM Journal on Computing, Vol. 24, No. 4 | 31 July 2006AbstractPDF (1868 KB)The complexity of searching succinctly represented graphsAutomata, Languages and Programming | 7 June 2005 Cross Ref A note on the complexity of local search problemsInformation Processing Letters, Vol. 53, No. 2 | 1 Jan 1995 Cross Ref A new adaptive multi-start technique for combinatorial global optimizationsOperations Research Letters, Vol. 16, No. 2 | 1 Sep 1994 Cross Ref On Finding and Verifying Locally Optimal SolutionsMark W. KrentelSIAM Journal on Computing, Vol. 19, No. 4 | 13 July 2006AbstractPDF (1078 KB)The Traveling Salesman ProblemCombinatorial Optimization Cross Ref The Traveling Salesman ProblemCombinatorial Optimization Cross Ref Das Traveling-Salesman-ProblemKombinatorische Optimierung Cross Ref Volume 21, Issue 3| 1992SIAM Journal on Computing407-599 History Submitted:09 January 1991Accepted:02 July 1991Published online:31 July 2006 InformationCopyright © 1992 © Society for Industrial and Applied MathematicsKeywordslocal searchtraveling salesman problemPLS-completePDF Download Article & Publication DataArticle DOI:10.1137/0221030Article page range:pp. 450-465ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics