Hacker News Reader

Comment by esafak | Hacker News Reader

Once you admit approximations the theoretical problem trades places with a more interesting one: what is the Pareto frontier of loss vs complexity?

View on HN

This is still a theoretical problem. Whether or not a particular problem class admits and approximation or an arbitrarily good approximation is often of theoretical interest.

One interesting example is metric TSP versus general TSP. We are used to traveling salesman problem on a map with distances that obey the triangle inequality. This admits an easy heuristic solution to an approximation factor of 2 (just do minimum spanning tree twice). However, nonmetric TSP is not approximable (to a constant factor of the optimal value in polynomial time (unless P=NP)).

Does minimum spanning tree rely on the triangle inequality? I thought it worked on arbitrary graphs

You’re right, it doesn’t. However, in TSP you are allowed to visit each vertex *exactly* once. So traversing the minimum spanning tree naively is not a valid solution. What you the approximation does is to „shortcut“ the paths if you would revisit an already seen vertex again. That’s where you need the triangle inequality to guarantee that the shortcut isn’t longer than the path through the minimum spanning tree. Otherwise you cannot guarantee an approximation ratio of at most 2.

So we see that a slight modification of the problem makes the approximation work for all graphs.

Elaborate on the proposed modification — are you referring to the fact that this can be done if distances obey a metric function?

If you modify the problem to allow passing by a node that you've already visited then the spanning tree approximation works for all graphs.

Reply on news.ycombinator.com