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).[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 I. Serdyukov, who discovered it independently in 1976.[2][3][4]

This algorithm still stands as the best polynomial time approximation algorithm that has been thoroughly peer-reviewed by the relevant scientific community for the traveling salesman problem on general metric spaces. In July 2020 however, Karlin, Klein, and Gharan released a preprint in which they introduced a novel approximation algorithm and claimed that its approximation ratio is 1.5 − 10−36. Their method 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.[5][6] The paper was published at STOC'21[7] where it received a best paper award.[8]

Algorithm

Let G = (V,w) be an instance of the travelling salesman problem. 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).

Then the algorithm can be described in pseudocode as follows.[1]

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

The steps 5 and 6 do not necessarily yield only one result. As such the heuristic can give several different paths.

Approximation ratio

The cost of the solution produced by the algorithm is within 3/2 of the optimum. To prove this, let C be the optimal traveling salesman tour. Removing an edge from C produces a spanning tree, which must have weight at least that of the minimum spanning tree, implying that w(T) ≤ w(C). Next, number the vertices of O in cyclic order around C, and partition C 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 O that matches the two endpoints of each path, and the weight of this matching is at most equal to the weight of the paths. Since these two sets of paths partition the edges of C, one of the two sets has at most half of the weight of C, and thanks to the triangle inequality its corresponding matching has weight that is also at most half the weight of C. The minimum-weight perfect matching can have no larger weight, so w(M) ≤ w(C)/2. Adding the weights of T and M gives the weight of the Euler tour, at most 3w(C)/2. Thanks to the triangle inequality, shortcutting does not increase the weight, so the weight of the output is also at most 3w(C)/2.[1]

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 3/2. One such class of inputs are formed by a path of n vertices, with the path edges having weight 1, together with a set of edges connecting vertices two steps apart in the path with weight 1 + ε 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 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. However, the optimal solution uses the edges of weight 1 + ε together with two weight-1 edges incident to the endpoints of the path, and has total weight (1 + ε)(n − 2) + 2, close to n for small values of ε. Hence we obtain an approximation ratio of 3/2.[9]

Example
Given: complete graph whose edge weights obey the triangle inequality
Calculate minimum spanning tree T
Calculate the set of vertices O with odd degree in T
Form the subgraph of G using only the vertices of O
Construct a minimum-weight perfect matching M in this subgraph
Unite matching and spanning tree T ∪ M 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.

References
  1. Goodrich, Michael T.; Tamassia, Roberto (2015), "18.1.2 The Christofides Approximation Algorithm", Algorithm Design and Applications, Wiley, pp. 513–514.
  2. Christofides, Nicos (1976), Worst-case analysis of a new heuristic for the travelling salesman problem (PDF), Report 388, Graduate School of Industrial Administration, CMU, archived (PDF) from the original on July 21, 2019
  3. van Bevern, René; Slugina, Viktoriia A. (2020), "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem", Historia Mathematica, 53: 118–127, arXiv:2004.02437, doi:10.1016/j.hm.2020.04.003, S2CID 214803097
  4. Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [On some extremal walks in graphs] (PDF), Upravlyaemye Sistemy (in Russian), 17: 76–79
  5. Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis (2020-08-30). "A (Slightly) Improved Approximation Algorithm for Metric TSP". arXiv:2007.01409 [cs.DS].
  6. Klarreich, Erica (8 October 2020). "Computer Scientists Break Traveling Salesperson Record". Quanta Magazine. Retrieved 2020-10-10.
  7. Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis (2021-06-15), "A (slightly) improved approximation algorithm for metric TSP", Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, New York, NY, USA: Association for Computing Machinery, pp. 32–45, arXiv:2007.01409, doi:10.1145/3406325.3451009, ISBN 978-1-4503-8053-9, retrieved 2022-04-20
  8. "ACM SIGACT - STOC Best Paper Award". www.sigact.org. Retrieved 2022-04-20.
  9. Bläser, Markus (2008), "Metric TSP", in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms}, Springer-Verlag, pp. 517–519, ISBN 9780387307701.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.