Hacker News new | ask | show | jobs
by bjourne 1519 days ago
You are correct for Metric TSP (weights satisfying the triangle inequality) but not for Euclidean TSP.
1 comments

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.