[Solved]: What is the asymptotic runtime of the best known TSP solving algorithm?

Problem Detail: 

I always thought that TSP currently requires time exponential in the number of cities to solve.

How, then, has Concorde optimally solved a TSP instance with 85,900 cities?!?

Is this a typo? Is the base of the exponential 1.0000000000000001 or similar? Was it an instance specifically constructed to be solvable easily? What is the asymptotic runtime of the best known TSP solving algorithm?

Asked By : user16732

Answered By : Juho

The worst case running time of Concorde or any other known method is exponential in the size of the input. However, sometimes heuristics or other pruning techniques are effective and you are able to solve some, even large, instances pretty quickly. You should define exactly what you mean by TSP as there are many variants, and many algorithms with different worst case run times.

See the accepted answer in this question on CSTheory to see a list of algorithms.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23731