For many years Lin–Kernighan–Johnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best known solutions for all other TSPs on which the method had been tried.
Impressive, so what is the complexity of that algorithm? Does the algorithm often work faster than predicted based on theoretical complexity (if yes, how much)? Is that algorithm used most often in software that solves the TSP?
Asked By : Ted Ersek
Answered By : rphv
…produces optimum results with high frequency, in running times that grow about as $n^2$.
The iterated Lin-Kernighan variant, proposed by Johnson in 1990, offers an observed improvement to $O(n^{1.25})$; an experimental treatment of this and many other local optimization TSP heuristics can be found here.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13380
