[1] 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 (Russian: Анатолий Иванович Сердюков).
That is, G is a complete graph on the set V of vertices, and the function w assigns a nonnegative real weight to every edge of G. According to the triangle inequality, for every three vertices u, v, and x, it should be the case that w(uv) + w(vx) ≥ w(ux).
[1] Steps 5 and 6 do not necessarily yield only a single result; as such, the heuristic can give several different paths.
The worst-case complexity of the algorithm is dominated by the perfect matching step, which has
complexity,[4] because the author was only aware of a less efficient perfect matching algorithm.
[1] There exist inputs to the travelling salesman problem that cause the Christofides algorithm to find a solution whose approximation ratio is arbitrarily close to 3/2.
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 n − 1, and the only two odd vertices will be the path endpoints, whose perfect matching consists of a single edge with weight approximately n/2.
The union of the tree and the matching is a cycle, with no possible shortcuts, and with weight approximately 3n/2.
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.
[9] 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.