Approximations of the Euclidean metric traveling salesman problem
Back in the good ol’ agrégation days, I remember I used as développement1 a nice 2-approx algorithm for the traveling salesman problem where the weights on the edges are given by the Euclidean distance between nodes.
I was told it was Christofides algorithm but actually it was not. It is the “double-tree algorithm”.
- Find a minimum spanning tree $T$ using e.g. Kruskal’s algorithm.
- Duplicate the edges of $T$. Find an Eulerian tour (that exists) using e.g. Hierholzer’s algorithm.
- Shortcut the Eulerian tour. This is a 2-approx of the (Euclidean) metric TSP.
It was hard to find who discovered it but Rozenkrantz et al. say that it is a “widely known but unpublished method” (1977). Christofides and Serdyukov found in 1976 (published in 1978) that by solving a matching problem between nodes of odd order (at the cost of $O(n^3)$), they could improve the approximation ratio to 3/2. This reminds me of the trick used by ENS Ulm team in Google Hash Code 2014.
To know more, you can check this other post.
References
Rosenkrantz, Daniel J., Richard E. Stearns, and Philip M. Lewis, II. “An analysis of several heuristics for the traveling salesman problem.” SIAM journal on computing 6.3 (1977): 563-581.
Christofides, N. “Worst-case analysis of a new heuristic for the traveling salesman problem.” Symp. on New Directions and Recent Results in Algorithms and Complexity (April 1976), Carnegie-Mellon University, Pittsburgh
Serdyukov, Anatoliy (1978), “О некоторых экстремальных обходах в графах” [On some extremal walks in graphs], Upravlyaemye Sistemy (Управляемые системы) (in Russian), 17: 76–79
-
This must mean nothing to non-French people but anyway. ↩