Hacker News Reader

Comment by yongjik | Hacker News Reader

But sorting has a known O(N log N) algorithm. Nobody sorts by comparing all N! permutations and picking the correct one. (Well, I certainly don't.)

On the other hand, TSP almost certainly does not have any O(N^k) algorithm, for any fixed k. Sure, the difference between (say) N^200 and N! is huge, but an introductory article cannot explain every details.

Saying that TSP is as hard as N! is technically wrong, but it's much less wrong than saying sorting is as hard as N!.

His posts read more like an advertisement for his research area (optimization) than actual complaint. Well, that's not a bad thing, but I feel the title is a bit clickbait-ish...

View on HN

But sorting has a known O(N log N) algorithm. Nobody sorts by comparing all N! permutations and picking the correct one. (Well, I certainly don't.)

That is precisely the point of the blog post. Nobody compares all N! permutation for sorting, and nobody checks all N! tours when solving a TSP. The latter is less trivial because algorithms that solve the TSP are far more sophisticated than a sorting algorithm, but they still avoid enumerating a very large subset of solutions. They cannot be claimed to run in polynomial time for any instance, but they are still quite efficient.

Saying that TSP is as hard as N! is technically wrong, but it's much less wrong than saying sorting is as hard as N!.

I disagree, both from a practical standpoint (in both cases there are orders of magnitude between N! and actual CPU time) and a more metaphysical one (neither algorithm explores the full set of solutions).

> Nobody compares all N! permutation for sorting, and nobody checks all N! tours when solving a TSP.

Doesn't this depend on what you mean by 'solve'? If you really want the single best solution, you're stuck with checking all N! solutions. If you want a solution which merely works pretty well almost all of the time, then you're right, there are many polynomial time solutions.

I wasn't able to read the Scientific American article that the author ranted against, but if it's discussing TSP from a mathematical standpoint, I wouldn't fault them for discussing the feasibility of checking all N! permutations... that's exactly how it was discussed to me in my introductory computation classes.

> "you're stuck with checking all N! solutions"

not quite -- once you have a solution that runs in time X, you no longer need to check any solution that has a sub-component that is known to take longer than time X. So, for example, if you find that going between locations A, C, J, F, P, E, and Q in that order takes longer than your current best whole-map solution, then you no longer have to check any solution of which ACJFPEQ is a subset. You can eliminate whole categories of solutions with a single check, instead of having to test each of them one-by-one.

So, memoization, a basic optimization technique.

Yes, the easiest example of optimization to give was a basic example. There are much better techniques too.

If you really want the single best solution, you're stuck with checking all N! solutions.

Agree with lotharbot here. You are as stuck with checking all N! solutions as a sorting algorithm would be. A good TSP algorithm won't, and nor will a sorting algorithm.

Just as sorting has a vast set of solutions, the best of which we can find in guaranteed O(n log n) time, a TSP problem admits an algorithm (branch-and-cut) that does not enumerate N! solutions, and actually a lot fewer.

The tricky part is that branch-and-bound and branch-and-cut algorithms (such as the one developed by Cook et al.) are implicit enumeration schemes, in that are proven to obtain the best solution of the N! without actually visiting all of them.

> If you really want the single best solution, you're stuck with checking all N! solutions.

No, you're not. There is an exact dynamic programming algorithm that takes O(n^2 2^n) time, which is exponential but much smaller than O(n!).

It is from Bellman, Held and Karp [0] and has O*(2^n) complexity for both space and time. It is quite simple and based on the idea that

"Every subpath of a path of minimum distance is itself of minimum distance."

[0] https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm

The linked post mentions a previous post [1] where he mentions that proving you have the optimal path doesn't always require N! cost:

> If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. In fact, I would be really interested in knowing the smallest “real” instance that Concorde cannot solve in, say, one day, on a normal laptop computer.

Note the "provably" before "optimal solution".

1: http://mat.tepper.cmu.edu/blog/?p=6995

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.

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.

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".

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?

>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

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!

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.

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?

If any path segments/lines intersect/cross on any plane, then the path is not a solution.

I think the point is that random lines in space (dimension > 2) intersect with probability 0, and so that shortcut almost never applies.

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".

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.

Sounds like something that would be easy to simulate and measure.

Also, the hull needn't be convex.

> Nobody sorts by comparing all N! permutations and picking the correct one. (Well, I certainly don't.)

You can usually make a problem seem harder than it actually (from a complexity point of view) is by phrasing it in terms of directly picking from permutations or combinations.

An example: finding the longest common substring for N strings can also be phrased as picking from a quadratic number of of substrings, but has a linear-time algorithm (using suffix trees).

Sorting is done by using information from comparisons to discard something like 50% of the remaining possible permutations at once.

Reply on news.ycombinator.com