3 ms·
>I suspect such a reduction would significantly inflate the size of your problem. If Metric TSP and a more general TSP are both NP-complete then there is an al
by jsprogrammer 10y ago
>I suspect such a reduction would significantly inflate the size of your problem.
If Metric TSP and a more general TSP are both NP-complete then there is an algorithm in P to transform a general TSP to a Metric TSP. So, a reduction could inflate the size of the problem, but that inflation will not be significant relative to the most naive approach.
Here is a SE algorithm: http://cstheory.stackexchange.com/a/14049 http://cstheory.stackexchange.com/a/14049
- zzazzdsa 10y agoThere's a more fundamental issue here-- when talking about approximation algorithms reductions don't necessarily preserve approximation ratios. If you take a standard TSP instance with optimal tour length C and add the largest distance between two points M to every edge, you get a new (metric) TSP with optimal tour length C + nM, where n is the number of nodes of the graph. Applying the Christofides algorithm to this new metric TSP instance can only guarantee a tour of length 1.5C + 1.5nM, and when you subtract M from every edge again to get a tour in the original TSP instance, this scheme will return a tour of length at most 1.5C + .5nM, a bound which is provably tight. This is a terrible approximate solution, since if the largest two-node distance is O(C) (for example), the approximation obtained has value O(n)C-- a monstrously bad O(n) approximation!