News for hackers. Stuff that matters.
Re:“American Scientist” Understands Nothing about the Travel... by btilly on Tuesday April 26, 2016 @04:26PM (#11575325)
Well yes..and no.

Let M be the largest distance between any two points in your graph. Add M to the length of every edge. Now the triangle inequality is trivially satisfied and you've got a Metric TSP.

However the "you find a path within a factor of 3/2 of the best possible" guarantee of the Christofides algorithm is much less useful than you might hope because all paths just got a lot longer.

There are no comments on this comment yet.