Metric travelling salesman problem

This is the travelling salesman problem on a complete graph with nonnegative symmetric distances satisfying the triangle inequality. Repeated visits can be shortcut without increasing cost. Assigning distance one to edges of an input graph and two to its nonedges creates a metric instance with a tour of cost at most the number of vertices exactly when the graph has a Hamiltonian cycle. Thus the metric problem remains NP-hard.

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 $3/2$-approximation algorithm for symmetric metric instances.