Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
The Concorde website claims that the problem instance was solved optimally. How can that be known for certain if heuristics were used? –  user16732 Apr 13 at 7:54
1  
@user16732 They probably use methods that prune the search tree safely, i.e. branch & bound. –  Juho Apr 13 at 7:57
    
Why does that not work for every instance? –  user16732 Apr 13 at 7:58
    
@user16732 The time taken by B&B is still exponential in the worst case. The time depends on the structure of your input, and parameters of your search. –  Juho Apr 13 at 8:03
1  
The size of an instance is not really what matters, but it's the structure of the instance. Even really large instances can be solved quickly, if the structure is easy. I don't know if Concorde even uses B&B, or some other similar methods. But this conclusion still holds. –  Juho Apr 13 at 8:07
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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