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 Scholar2 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 Scholar3 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 Scholar4 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 Scholar5 B. W. Kernighan and , S. Lin, An efficient heuristic procedure for partitioning graphs, Bell S. T. J., 49 (1970), 291–307 0333.05001 CrossrefGoogle Scholar6 M. W. Krentel, On Finding Locally Optimal Solutions, Proceedings of the 4th Structures Conference, 1989 Google Scholar7 M. W. Krentel, 1989, manuscript Google Scholar8 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 Scholar9 G. Lueker, 1975, manuscript, Princeton University, Princeton, NJ Google Scholar10 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 Scholar11 C. H. Papadimitriou, On graph-theoretic lemmata and complexity classes, Proceedings on Foundations of Computer Science, 1990 Google Scholar12 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 Scholar13 C. H. Papadimitriou, , A. A. Schäffer and , M. Yannakakis, On the complexity of local search, Proc. STOC Conference, 1990 Google Scholar14 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