2
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ The Concorde website claims that the problem instance was solved optimally. How can that be known for certain if heuristics were used? $\endgroup$
    – user16732
    Commented Apr 13, 2014 at 7:54
  • 1
    $\begingroup$ @user16732 They probably use methods that prune the search tree safely, i.e. branch & bound. $\endgroup$
    – Juho
    Commented Apr 13, 2014 at 7:57
  • $\begingroup$ Why does that not work for every instance? $\endgroup$
    – user16732
    Commented Apr 13, 2014 at 7:58
  • $\begingroup$ @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. $\endgroup$
    – Juho
    Commented Apr 13, 2014 at 8:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Juho
    Commented Apr 13, 2014 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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