Christofides algorithm

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 ( ). Christofides published the algorithm in 1976¹; Serdyukov discovered it independently in 1976 but published it in 1978.

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 ( ). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978. ===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. ==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 . One such class of inputs are formed by a path of vertices, with the path edges having weight , together with a set of edges connecting vertices two steps apart in the path with weight for a number 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 , and the only two odd vertices will be the path endpoints, whose perfect matching consists of a single edge with weight approximately . The union of the tree and the matching is a cycle, with no possible shortcuts, and with weight approximately . However, the optimal solution uses the edges of weight together with two weight- edges incident to the endpoints of the path, and has total weight , close to for small values of . Hence we obtain an approximation ratio of 3/2. ==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 −36 . 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+\tfrac1c times the optimal for geometric instances of TSP in O\left(n (\log n)^{(O(c \sqrt{d}))^{d-1}}\right) 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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1366212096 under CC BY-SA 4.0; modifications have been made.