Jump to content

Christofides algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Altenmann (talk | contribs) at 02:13, 24 November 2023. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 (Template:Lang-ru), who discovered it independently in 1976.<refname=cri>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 </ref>[2][3]

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.

Computational complexity

The worst-case complexity of the algorithm is dominated by the perfect matching step, which has O(n^3) complexity.Cite error: A <ref> tag is missing the closing </ref> (see the help page).

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.

Improvements

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. Theirs is a randomized algorithm and 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.[4][5] The paper was published at STOC'21[6] where it received a best paper award.[7]

References

  1. ^ a b Goodrich, Michael T.; Tamassia, Roberto (2015), "18.1.2 The Christofides Approximation Algorithm", Algorithm Design and Applications, Wiley, pp. 513–514.
  2. ^ 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
  3. ^ Serdyukov, Anatoliy (1978), "О некоторых экстремальных обходах в графах" [On some extremal walks in graphs] (PDF), Upravlyaemye Sistemy (Управляемые системы) (in Russian), 17: 76–79
  4. ^ Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis (2020-08-30). "A (Slightly) Improved Approximation Algorithm for Metric TSP". arXiv:2007.01409 [cs.DS].
  5. ^ Klarreich, Erica (8 October 2020). "Computer Scientists Break Traveling Salesperson Record". Quanta Magazine. Retrieved 2020-10-10.
  6. ^ 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 (2023 version)
  7. ^ "ACM SIGACT - STOC Best Paper Award". www.sigact.org. Retrieved 2022-04-20.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Christofides_algorithm&oldid=1186567146"