| ▲ | LPisGood 3 hours ago | |
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)). | ||
| ▲ | inigyou an hour ago | parent [-] | |
Does minimum spanning tree rely on the triangle inequality? I thought it worked on arbitrary graphs | ||