4 ms·

I have seen many TSP solvers that enumerate known incorrect solutions. For example, a TSP solution will have no intersecting paths, but many solvers will genera

I have seen many TSP solvers that enumerate known incorrect solutions. For example, a TSP solution will have no intersecting paths, but many solvers will generate and check solutions with intersecting paths all day long.

gamegoblin 10y ago
Your heuristic is only valid for the Metric TSP problem, not the general TSP problem. That is, graphs do not need to be embedded in some physical space in which "intersecting paths" exist.
- jsprogrammer 10y ago
  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".
  - gamegoblin 10y ago
    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?
    - 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 ago
        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!
    - btilly 10y 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.
  - yongjik 10y ago
    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?
    - jsprogrammer 10y ago
      If any path segments/lines intersect/cross on any plane, then the path is not a solution.
      - bmm6o 10y ago
        I think the point is that random lines in space (dimension > 2) intersect with probability 0, and so that shortcut almost never applies.
        jsprogrammer 10y ago
        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".
        yongjik 10y ago
        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.
        jsprogrammer 10y ago
        Sounds like something that would be easy to simulate and measure. Also, the hull needn't be convex.

gamegoblin 10y ago

Your heuristic is only valid for the Metric TSP problem, not the general TSP problem. That is, graphs do not need to be embedded in some physical space in which "intersecting paths" exist.

jsprogrammer 10y ago
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".
- gamegoblin 10y ago
  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?
  - 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 ago
      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!
  - btilly 10y 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.
- yongjik 10y ago
  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?
  - jsprogrammer 10y ago
    If any path segments/lines intersect/cross on any plane, then the path is not a solution.
    - bmm6o 10y ago
      I think the point is that random lines in space (dimension > 2) intersect with probability 0, and so that shortcut almost never applies.
      - jsprogrammer 10y ago
        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".
        yongjik 10y ago
        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.
        jsprogrammer 10y ago
        Sounds like something that would be easy to simulate and measure. Also, the hull needn't be convex.