Christofides' algorithm

from Wikipedia, the free encyclopedia

The algorithm of Christofides or the algorithm of Christofides and Serdyukov is an algorithm that for the approximation of the metric of the traveling salesman problem is used. It was discovered in 1976 independently by Nicos Christofides and Anatoliy I. Serdyukov and has long been the best approximation of the problem for Euclidean graphs. In 1996, however, Arora and Mitchell presented a better PTAS for these .

The formal approach is similar to that of the minimum spanning tree heuristic :

  1. Generate a minimal spanning tree  for the underlying graph with edge weights.
  2. Find a minimal perfect match (in terms of edge weight) in the graph between the nodes that have odd degrees in the tree just created .
  3. Add these edges to . Multi-edges can occur. The resulting graph  is then Eulerian .
  4. Construct an Euler tour in  .
  5. Construct a Hamilton cycle in . To do this, choose any starting node and take the Euler tour. Replace the already visited nodes with direct connections (or abbreviations) to the next not yet visited node.

Quality guarantee

It can be shown that the Christofides heuristic is a 1.5 approximation. This means that the resulting round trip is a maximum of half longer than the optimal tour. The proof is based on repeated application of the triangle inequality .

  • The sum of the edge weights in the Minimum Spanning Tree (MST) is anyway less than or equal to the optimal solution, since every solution of the Traveling Salesman Problem (TSP) contains a spanning tree .
  • Regarding the matching, the following applies:
    Let the sequence of nodes previously of odd degree in the optimal solution; therebetween are any other nodes: . Consider the two matchings as well . Then, due to the triangle inequality, the following applies that the total costs of the optimal solution are greater than or equal to those of any two matchings, in particular two times the minimum matching. Then a minimal matching is only a maximum of half the size of the optimal solution. In this way the sum of the edge weights along the Euler tour in (i.e. the sum of the weights of all edges in ) can be estimated upwards.
  • Finally, the sum of the edges in the Hamilton circle generated from the Euler tour can be estimated by applying the triangle inequality upwards again using the sum of the edges in the Euler tour (because the direct edges cannot be longer than the connection via a previously visited node), i.e. transitively by 1.5 times the optimal solution.

example

Metric graph with 5 nodes Starting point: metric graph with edge weights
Christofides MST.svg Calculate the minimum spanning tree .
V'.svg Determine the set of nodes with odd degrees in the spanning tree ( ).
G V'.svg reduce to the nodes from ( ).
Christofides Matching.svg Determine matching with minimal weight on .
TuM.svg Combine matching and spanning tree ( ). This step ensures that nodes that previously had an odd degree now have an even degree. This is a necessary condition for calculating the Euler tour in the next step.
Eulertour.svg Calculate Euler tour (ABCADEA).
Eulertour adjusted.svg Remove nodes that occur repeatedly and replace with a direct connection (AB- CD- EA). In metric graphs, this does not result in a longer distance.

This tour is the output of the algorithm.

literature

  • Lawler, Lenstra, Rinnooy Kan, Shmoys (Eds.): The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization . Wiley, Chichester 1985. ISBN 0-471-90413-9 , Section 5.3.4: Christofides' algorithm

Web links

Individual evidence

  1. ^ N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem , Report 388, Graduate School of Industrial Administration, Carnegie Mellon University (CMU), 1976
  2. Anatoliy I. Serdyukov: About some extreme circles in graphs . In: Upravlyaevye Sistemy . tape 17 . Novosibirsk 1978, p. 76–79 (Russian, nsc.ru [PDF] Original title: О некоторых экстремальных обходах в графах .).
  3. ^ René van Bevern, Viktoriia A. Slugina: A historical note on the 3/2 approximation algorithm for the metric traveling salesman problem . In: Historia Mathematica . Elsevier, 2020, doi : 10.1016 / j.hm.2020.04.003 , arxiv : 2004.02437 .