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?