8 ms·
It is, but there are polynomial-time approximation algorithms that can get you arbitrarily close to the optimum.
by unnah 5y ago
It is, but there are polynomial-time approximation algorithms that can get you arbitrarily close to the optimum.
- jhgb 5y agoNo, 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?
- unnah 5y agoEuclidean 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.
- jhgb 5y agoWell, 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.
- bjourne 5y agoYou are correct for Metric TSP (weights satisfying the triangle inequality) but not for Euclidean TSP.
- a3_nm 5y agoFurther, 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 https://en.wikipedia.org/wiki/Christofides_algorithm.