While the algorithm you mention does NOT solve the SYMMETRIC TSP to optimality, it is indeed polynomial. Here is the original paper on the subject: 

http://pubsonline.informs.org/doi/abs/10.1287/opre.21.2.498

And here is a classic paper on the complexity analysis of a version of the algorithm, used for finding local optima:

http://epubs.siam.org/doi/pdf/10.1137/0221030

That is great. What about the Iterated Lin-Kernighan method? Is it reasonable to think it is the same or even better?

Hi Patricia,

Do you mean "Chained" Lin-Kernighan? The results obtained by this method are claimed to be outstanding. It was initially designed by Martin et al. but I think you should take a look at Applegate's et al. paper on the topic.

http://www.math.uwaterloo.ca/~bico/papers/clk_ijoc.pdf

Also, I may not have understood your question very well, but I don't think that applying a method several times (designing a chained version of it) can reduce its complexity.

I hope this helped,

Best regards,

Imène.

Imene, 

It has helped a lot many thanks.  The paper is very useful too. 

Patricia 

Hi Patricia

Actually,  the best implementation of Lin-Kernigan is probably by K. Helsgaun. This was the algorithm used by the Concorde people to solve the largest problem instance in TSP (84900 cities). You can get articles about it and download it from:

http://www.akira.ruc.dk/~keld/research/LKH/

Best Regards Thomas

For the 2-opt neighborhood, it is known that there exist TSP instances for which an exponentially large number of moves is needed to reach a local minimum.  The problem of finding a local minimum with respect to 2-opt is not known to be polynomial-time solvable, but is not known to be NP-complete either.  Such problems are called "PLS-complete".  See here:

http://en.wikipedia.org/wiki/PLS_(complexity)

My guess is that finding a local minimum for the Lin-Kernigan neighbourhood will be PLS-complete as well, but I am not aware of a formal proof.