- See also
- References
- External links
{{about|the heuristic for the travelling salesman problem|a heuristic algorithm for the graph partitioning problem|Kernighan–Lin algorithm}}In combinatorial optimization, Lin–Kernighan is one of the best heuristics for solving the symmetric travelling salesman problem. Briefly, it involves swapping pairs of sub-tours to make a new tour. It is a generalization of 2-opt and 3-opt. 2-opt and 3-opt work by switching two or three edges to make the tour shorter. Lin–Kernighan is adaptive and at each step decides how many paths between cities need to be switched to find a shorter tour. See also- Local search (optimization)
References- {{cite journal|doi=10.1287/opre.21.2.498|first1=Shen|last1=Lin|authorlink1=Shen Lin|first2=B. W.|last2=Kernighan|authorlink2=Brian Kernighan| year = 1973 | title = An Effective Heuristic Algorithm for the Traveling-Salesman Problem | journal = Operations Research | volume = 21|issue=2 | pages = 498–516}}
- {{cite journal|doi = 10.1016/S0377-2217(99)00284-2|author = K. Helsgaun |title= An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic |journal=European Journal of Operational Research |volume= 126 |issue= 1 |year=2000 |pages=106–130 |citeseerx = 10.1.1.180.1798 }}
- {{cite book|chapter-url=http://www.research.att.com/~dsj/papers/TSPchapter.pdf|chapter=The Traveling Salesman Problem: A Case Study in Local Optimization|first1=David S.|last1=Johnson|first2=Lyle A.|last2=McGeoch|title=Local Search in Combinatorial Optimization|editors=E. H. L. Aarts and J. K. Lenstra|publisher=John Wiley and Sons|location=London|year=1997|pages=215–310}}
External links{{DEFAULTSORT:Lin-Kernighan heuristic}}{{algorithm-stub}}{{mathapplied-stub}} 4 : Combinatorial optimization|Combinatorial algorithms|Heuristic algorithms|Travelling salesman problem |