News for hackers. Stuff that matters.
Re:“American Scientist” Understands Nothing about the Travel... by Strilanc on Tuesday April 26, 2016 @05:51PM (#11576006)
The linked post mentions a previous post [1] where he mentions that proving you have the optimal path doesn't always require N! cost:

> If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. In fact, I would be really interested in knowing the smallest “real” instance that Concorde cannot solve in, say, one day, on a normal laptop computer.

Note the "provably" before "optimal solution".

1: http://mat.tepper.cmu.edu/blog/?p=6995

There are no comments on this comment yet.