The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
Author:
- Christos H. PapadimitriouCPChristos H. Papadimitriou
- 1 June 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (3) , 450-465
Abstract
It 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.Keywords
This publication has 8 references indexed in Scilit:
- On total functions, existence theorems and computational complexityTheoretical Computer Science, 1991
- Simple Local Search Problems that are Hard to SolveSIAM Journal on Computing, 1991
- On Finding and Verifying Locally Optimal SolutionsSIAM Journal on Computing, 1990
- On the complexity of local search1990
- How easy is local search?Journal of Computer and System Sciences, 1988
- Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 1982
- An Effective Heuristic Algorithm for the Traveling-Salesman ProblemOperations Research, 1973
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970