Comment on Can you be sure to clear a line at Tetris?parentComments−bjourne4yYou are correct for Metric TSP (weights satisfying the triangle inequality) but not for Euclidean TSP.−a3_nmOP4yFurther, 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
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.