Most NP-complete problems have really good heuristics that come to within a hair of optimal on most useful real-world inputs, e.g. things like integer partitioning, bin packing, traveling salesman, etc. You need really unusual inputs to give an optimal solver a drastic advantage. Case in point, with real-world TSP the fact that the cities are embedded on a plane means their distances have constraints that don't exist in the general problem.
No, there aren't? The last time I checked, the best polynomial-time approximation algorithm to symmetric TSP (Christofides) could only guarantee finding a tour with no more than 3/2 of optimal length. Has something better been found since then?
Euclidean TSP is easier than general symmetric TSP. Polynomial-time approximation schemes (PTAS) were discovered in parallel by Arora (1998) and Mitchell (1999). AFAIK those algorithms are not very practical though. I haven't followed subsequent work in any detail, but I haven't heard of any major breakthroughs since then.
Well, damn. I imagine the reason why didn't know about this is because I have never been able to formulate any of my particular problems in terms of Euclidean TSP (even just metric was hard enough at times), so all interesting stuff was about metric TSP for me. I'll have to look at that work, though. Thanks for the pointers.
Further, for metric TSP, an approximation algorithm with a slightly better ratio was found, and received a best paper award at STOC'21. See the second paragraph of https://en.wikipedia.org/wiki/Christofides_algorithm.
Comments
Most NP-complete problems have really good heuristics that come to within a hair of optimal on most useful real-world inputs, e.g. things like integer partitioning, bin packing, traveling salesman, etc. You need really unusual inputs to give an optimal solver a drastic advantage. Case in point, with real-world TSP the fact that the cities are embedded on a plane means their distances have constraints that don't exist in the general problem.
I'm pretty sure 2-D Euclidean TSP is NP-Hard.
https://en.m.wikipedia.org/wiki/Travelling_salesman_problem (Computational Complexity).
It is, but there are polynomial-time approximation algorithms that can get you arbitrarily close to the optimum.
No, there aren't? The last time I checked, the best polynomial-time approximation algorithm to symmetric TSP (Christofides) could only guarantee finding a tour with no more than 3/2 of optimal length. Has something better been found since then?
Euclidean TSP is easier than general symmetric TSP. Polynomial-time approximation schemes (PTAS) were discovered in parallel by Arora (1998) and Mitchell (1999). AFAIK those algorithms are not very practical though. I haven't followed subsequent work in any detail, but I haven't heard of any major breakthroughs since then.
Well, damn. I imagine the reason why didn't know about this is because I have never been able to formulate any of my particular problems in terms of Euclidean TSP (even just metric was hard enough at times), so all interesting stuff was about metric TSP for me. I'll have to look at that work, though. Thanks for the pointers.
You are correct for Metric TSP (weights satisfying the triangle inequality) but not for Euclidean TSP.
Further, for metric TSP, an approximation algorithm with a slightly better ratio was found, and received a best paper award at STOC'21. See the second paragraph of https://en.wikipedia.org/wiki/Christofides_algorithm.