Editing Travelling salesman problem (section)

==== The Algorithm of Christofides and Serdyukov ====
[[File:Creating a matching.png|thumb|Creating a matching]]
[[File:UbMjAyAmQrSwtP0gdeKe matchingshortcut.png|thumb|Using a shortcut heuristic on the graph created by the matching above]]

The [[Christofides algorithm|algorithm of Christofides and Serdyukov]] follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimum-weight [[perfect matching]]. This gives a TSP tour which is at most 1.5 times the optimal. It was one of the first [[approximation algorithm]]s, and was in part responsible for drawing attention to approximation algorithms as a practical approach to [[intractable problem]]s. As a matter of fact, the term "algorithm" was not commonly extended to approximation algorithms until later; the Christofides algorithm was initially referred to as the Christofides heuristic.<ref name="bs20" />

This algorithm looks at things differently by using a result from graph theory which helps improve on the lower bound of the TSP which originated from doubling the cost of the minimum spanning tree. Given an [[Eulerian graph]], we can find an [[Eulerian tour]] in {{tmath|O(n)}} time,<ref name="Wiley"/> so if we had an Eulerian graph with cities from a TSP as vertices, then we can easily see that we could use such a method for finding an Eulerian tour to find a TSP solution. By the [[triangle inequality]], we know that the TSP tour can be no longer than the Eulerian tour, and we therefore have a lower bound for the TSP. Such a method is described below.
# Find a minimum spanning tree for the problem.
# Create duplicates for every edge to create an Eulerian graph.
# Find an Eulerian tour for this graph.
# Convert to TSP: if a city is visited twice, then create a shortcut from the city before this in the tour to the one after this.

To improve the lower bound, a better way of creating an Eulerian graph is needed. By the triangle inequality, the best Eulerian graph must have the same cost as the best travelling salesman tour; hence, finding optimal Eulerian graphs is at least as hard as TSP. One way of doing this is by minimum weight [[Matching (graph theory)|matching]] using algorithms with a complexity of <math>O(n^3)</math>.<ref name="Wiley"/>

Making a graph into an Eulerian graph starts with the minimum spanning tree; all the vertices of odd order must then be made even, so a matching for the odd-degree vertices must be added, which increases the order of every odd-degree vertex by 1.<ref name="Wiley"/> This leaves us with a graph where every vertex is of even order, which is thus Eulerian. Adapting the above method gives the algorithm of Christofides and Serdyukov:

# Find a minimum spanning tree for the problem.
# Create a matching for the problem with the set of cities of odd order. 
# Find an Eulerian tour for this graph.
# Convert to TSP using shortcuts.