2 ms·
You are correct for Metric TSP (weights satisfying the triangle inequality) but not for Euclidean TSP.
by bjourne 5y ago
You 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.