The Traveling Salesman Problem

Metric TSP, the double-tree 2-approximation, and Christofides.

The idea

The traveling salesman problem asks, given $n$ cities and the distance between each pair, for the shortest closed tour that visits every city exactly once and returns to where it started. It is NP-hard: no polynomial-time algorithm for it is known, so the goal changes. Instead of the optimal tour length $\mathrm{OPT}$, we look for a polynomial-time algorithm together with a proof that the tour it returns is never longer than a fixed factor $\alpha$ times $\mathrm{OPT}$. Such an algorithm is called an $\alpha$-approximation, and $\alpha$ is a worst-case promise, holding for every instance.

No such promise is possible for arbitrary distances, so the standard assumption is that the distances are metric: they obey the triangle inequality $c(x, z) \le c(x, y) + c(y, z)$, which says going straight from $x$ to $z$ is never worse than detouring through $y$. This assumption is what permits shortcutting: a walk through the cities may repeat a city, and a repeat can be skipped in favor of the next city not yet visited, with the triangle inequality guaranteeing the result is no longer than what it replaced. The metric algorithms therefore share one plan: build a cheap walk that reaches every city, shortcut it into a genuine tour, and bound its length against $\mathrm{OPT}$. The simplest is the double-tree algorithm.

Algorithm.

Algorithm: Double-Tree Input: a metric instance — the cities and their pairwise distances Output: a tour of length at most 2 × OPT 1. build a minimum spanning tree T of the cities 2. double every edge of T // every degree is now even, so a closed walk uses each edge exactly once 3. follow that walk, shortcutting each repeated city to the next city not yet visited 4. return the resulting tour // the walk has length 2 × c(T); shortcutting never lengthens it

Christofides' algorithm follows the same plan but evens out the degrees more cheaply than doubling: instead of doubling every edge, it adds a minimum-weight perfect matching on the odd-degree vertices of the tree.

Theorem (Approximation guarantees for metric TSP).

On every metric instance, the double-tree algorithm returns a tour of length at most $2\,\mathrm{OPT}$, and Christofides' algorithm returns a tour of length at most $\tfrac{3}{2}\,\mathrm{OPT}$. Both run in polynomial time.

Ways to work on it

• Walkthrough. Approximation algorithms for the shortest tour, built from a spanning-tree lower bound.
• Practice. Apply an approximation ratio to bound the tour length.
• Hardest. Run an approximation algorithm end to end on a small instance.

Not sure where to start? Take the ten-question placement test.