4
$\begingroup$

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?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Please give an outline or a (peer-reviewed, published) reference for the algorithm. $\endgroup$ – Raphael♦ Jul 22 '13 at 14:16
  • 1
    $\begingroup$ Clearly in the worst case the algorithm is exponential, as otherwise it would solve P vs. NP. And if it's ever used in practice, it must often run faster than exponential, otherwise it would be wholly impractical. There may be a formalization of how much faster, but I don't know that it is if it exists. $\endgroup$ – jmite Jul 23 '13 at 19:12
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.