News for hackers. Stuff that matters.
Re:“American Scientist” Understands Nothing about the Travel... by jsprogrammer on Tuesday April 26, 2016 @02:13PM (#11574259)
All NP-complete problems should be reducible to the Metric TSP problem. You would only need to transform your more general problem to use this "heuristic".
Re:“American Scientist” Understands Nothing about the Travel... by gamegoblin on Tuesday April 26, 2016 @03:39PM (#11574916)
I suspect such a reduction would significantly inflate the size of your problem.

I say this because there exist algorithms such as Christofides algorithm which explicitly work on Metric TSP. If there were such a trivial transformation that preserved the complexity class, why wouldn't Christofides algorithm apply to the general case?

Re:“American Scientist” Understands Nothing about the Travel... by jsprogrammer on Tuesday April 26, 2016 @04:25PM (#11575321)
>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

Re:“American Scientist” Understands Nothing about the Travel... by zzazzdsa on Wednesday April 27, 2016 @01:47PM (#11582704)
There'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!
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.

Re:“American Scientist” Understands Nothing about the Travel... by yongjik on Tuesday April 26, 2016 @04:36PM (#11575415)
I'm no expert, but I don't think the "metric" in "Metric TSP problem" means "embeddable in a 2-D space." If you pick random points in a 500-dimensional space, the graph is metric.

But how do you define "intersecting paths" there?

Re:“American Scientist” Understands Nothing about the Travel... by jsprogrammer on Tuesday April 26, 2016 @04:43PM (#11575455)
If any path segments/lines intersect/cross on any plane, then the path is not a solution.
Re:“American Scientist” Understands Nothing about the Travel... by bmm6o on Tuesday April 26, 2016 @07:06PM (#11576497)
I think the point is that random lines in space (dimension > 2) intersect with probability 0, and so that shortcut almost never applies.
Re:“American Scientist” Understands Nothing about the Travel... by jsprogrammer on Tuesday April 26, 2016 @07:45PM (#11576710)
You should be able to "wrap a hull" around all the points. If there is no hull that can be wrapped without intersecting a path segment, the path is not a solution.

Basically you are checking for line-plane intersections. A solution should outline a "non-self-intersecting volume".

Re:“American Scientist” Understands Nothing about the Travel... by yongjik on Wednesday April 27, 2016 @12:42AM (#11577868)
Defining a convex hull in a 100-dimensional space requires 101 points. You can easily have a scenario where the only available "convex hull" is the one that contains the entire graph. In fact, I'm sure that a "randomly chosen" metric graph will be of this variety.
Re:“American Scientist” Understands Nothing about the Travel... by jsprogrammer on Wednesday April 27, 2016 @02:22AM (#11578208)
Sounds like something that would be easy to simulate and measure.

Also, the hull needn't be convex.