Compute a minimum spanning tree, then a minimum-weight perfect matching on its odd-degree vertices. Their multiset union is connected with even degrees, so it has an Euler circuit. Shortcut repeated vertices to obtain a metric tour. The tree costs at most the optimal tour, and shortcutting the optimal tour to its odd-degree subset gives a cyclic order whose alternating matchings show that the added matching costs at most half the optimum. The result is a polynomial-time -approximation algorithm for symmetric metric instances.
Articles by others on the same topic
Christofides' algorithm is a well-known polynomial-time approximation algorithm used to find a solution to the Metric Traveling Salesman Problem (TSP). The TSP involves finding the shortest possible route that visits a set of points (cities) and returns to the starting point, visiting each city exactly once. The original TSP can be NP-hard, but the Metric TSP is a special case where the distances between the cities satisfy the triangle inequality (i.e.