4 ms·
This is still a theoretical problem. Whether or not a particular problem class admits and approximation or an arbitrarily good approximation is often of theoret
by LPisGood 2mo 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 2mo agoDoes minimum spanning tree rely on the triangle inequality? I thought it worked on arbitrary graphs
- mockerell 2mo agoYou’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.
- inigyou 2mo agoSo we see that a slight modification of the problem makes the approximation work for all graphs.