3 ms·
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 trivi
by btilly 11y ago
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.