Christofides algorithm

Template:Short description Template:CS1 config The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality). It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and Anatoliy Serdyukov (Template:Langx). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978.

Algorithm

Let Template:Math be an instance of the travelling salesman problem. That is, Template:Mvar is a complete graph on the set Template:Mvar of vertices, and the function Template:Mvar assigns a nonnegative real weight to every edge of Template:Mvar. According to the triangle inequality, for every three vertices Template:Mvar, Template:Mvar, and Template:Mvar, it should be the case that Template:Math.

Then the algorithm can be described in pseudocode as follows.

1. Create a minimum spanning tree Template:Mvar of Template:Mvar.
2. Let Template:Mvar be the set of vertices with odd degree in Template:Mvar. By the handshaking lemma, Template:Mvar has an even number of vertices.
3. Find a minimum-weight perfect matching Template:Mvar in the subgraph induced in Template:Mvar by Template:Mvar.
4. Combine the edges of Template:Mvar and Template:Mvar to form a connected multigraph Template:Mvar in which each vertex has even degree.
5. Form an Eulerian circuit in Template:Mvar.
6. Make the circuit found in previous step into a Hamiltonian circuit by skipping repeated vertices (shortcutting).

Steps 5 and 6 do not necessarily yield only a single result; as such, the heuristic can give several different paths.

Computational complexity

The worst-case complexity of the algorithm is dominated by the perfect matching step, which has $O(n^3)$ complexity. Serdyukov's paper claimed $O(n^3\log n)$ complexity, because the author was only aware of a less efficient perfect matching algorithm.

Approximation ratio

The cost of the solution produced by the algorithm is within Template:Math of the optimum. To prove this, let Template:Mvar be the optimal traveling salesman tour. Removing an edge from Template:Mvar produces a spanning tree, which must have weight at least that of the minimum spanning tree, implying that Template:Math - lower bound to the cost of the optimal solution.

The algorithm addresses the problem that Template:Math is not a tour by identifying all the odd degree vertices in Template:Math; since the sum of degrees in any graph is even (by the Handshaking lemma), there is an even number of such vertices. The algorithm finds a minimum-weight perfect matching Template:Math among the odd-degree ones.

Next, number the vertices of Template:Mvar in cyclic order around Template:Mvar, and partition Template:Mvar into two sets of paths: the ones in which the first path vertex in cyclic order has an odd number and the ones in which the first path vertex has an even number. Each set of paths corresponds to a perfect matching of Template:Mvar that matches the two endpoints of each path, and the weight of this matching is at most equal to the weight of the paths. In fact, each path endpoint will be connected to another endpoint, which also has an odd number of visits due to the nature of the tour.

Since these two sets of paths partition the edges of Template:Mvar, one of the two sets has at most half of the weight of Template:Mvar, and thanks to the triangle inequality its corresponding matching has weight that is also at most half the weight of Template:Mvar. The minimum-weight perfect matching can have no larger weight, so Template:Math. Adding the weights of Template:Mvar and Template:Mvar gives the weight of the Euler tour, at most Template:Math. Thanks to the triangle inequality, even though the Euler tour might revisit vertices, shortcutting does not increase the weight, so the weight of the output is also at most Template:Math.

Lower bounds

There exist inputs to the travelling salesman problem that cause the Christofides algorithm to find a solution whose approximation ratio is arbitrarily close to Template:Math. One such class of inputs are formed by a path of Template:Mvar vertices, with the path edges having weight Template:Math, together with a set of edges connecting vertices two steps apart in the path with weight Template:Math for a number Template:Math chosen close to zero but positive.

All remaining edges of the complete graph have distances given by the shortest paths in this subgraph. Then the minimum spanning tree will be given by the path, of length Template:Math, and the only two odd vertices will be the path endpoints, whose perfect matching consists of a single edge with weight approximately Template:Math.

The union of the tree and the matching is a cycle, with no possible shortcuts, and with weight approximately Template:Math. However, the optimal solution uses the edges of weight Template:Math together with two weight-Template:Math edges incident to the endpoints of the path, and has total weight Template:Math, close to Template:Mvar for small values of Template:Math. Hence we obtain an approximation ratio of 3/2.

Example

	Given: complete graph whose edge weights obey the triangle inequality
	Calculate minimum spanning tree Template:Mvar
	Calculate the set of vertices Template:Mvar with odd degree in Template:Mvar
	Form the subgraph of Template:Mvar using only the vertices of Template:Mvar
	Construct a minimum-weight perfect matching Template:Mvar in this subgraph
	Unite matching and spanning tree Template:Math to form an Eulerian multigraph
	Calculate Euler tour Here the tour goes A->B->C->A->D->E->A. Equally valid is A->B->C->A->E->D->A.
	Remove repeated vertices, giving the algorithm's output. If the alternate tour would have been used, the shortcut would be going from C to E which results in a shorter route (A->B->C->E->D->A) if this is an euclidean graph as the route A->B->C->D->E->A has intersecting lines which is proven not to be the shortest route.

Further developments

This algorithm is no longer the best polynomial time approximation algorithm for the TSP on general metric spaces. Karlin, Klein, and Gharan introduced a randomized approximation algorithm with approximation ratio 1.5 − 10⁻³⁶. It follows similar principles to Christofides' algorithm, but uses a randomly chosen tree from a carefully chosen random distribution in place of the minimum spanning tree. The paper received a best paper award at the 2021 Symposium on Theory of Computing.

In the special case of Euclidean space of dimension $d$, for any $c>0$, there is a polynomial-time algorithm that finds a tour of length at most $1+\frac{1}{c}$ times the optimal for geometric instances of TSP in

$O(n(\log n{)}^{(O(c\sqrt{d}){)}^{d-1}})$ time.

For each constant $c$ this time bound is in polynomial time, so this is called a polynomial-time approximation scheme (PTAS). Sanjeev Arora and Joseph S. B. Mitchell were awarded the Gödel Prize in 2010 for their simultaneous discovery of a PTAS for the Euclidean TSP.

Methods based on the Christofides–Serdyukov algorithm can also be used to approximate the stacker crane problem, a generalization of the TSP in which the input consists of ordered pairs of points from a metric space that must be traversed consecutively and in order. For this problem, it achieves an approximation ratio of 9/5.

External links

• NIST Christofides Algorithm Definition