Complexity of the V-opt heuristic Traveling Salesman algorithm

Question

The paragraph on V-opt heuristic TSP algorithms at this site mentions a very effective algorithm due to Lin-Kernigham-Johnson. That page says:

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?

Answer 1

According to the original 1973 paper, the Lin-Kernighan algorithm

...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.