logoalt Hacker News

LPisGoodyesterday at 10:44 PM1 replyview 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)).


Replies

inigyoutoday at 12:47 AM

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