Related Problems: TSP Type: Constructive Algorithm Work on: Graph Complexity: O(n^3)

Description: fining Double Minimum Spanning Tree with the additional minimum-weight matching calculation. (This part is also the most time consuming one)
Tests have shown that Christofides’ algorithm tends to place itself around 10% above he Held-Karp lower bound., worst-case ratio 3/2,

Pseudo Code:
1. Build a minimal spanning tree from the set of all cities.
2. Create a minimum-weight matching (MWM) on the set of nodes having an odd degree. Add the MST together with the MWM.
3. Create an Euler cycle from the combined graph, and traverse it taking shortcuts to avoid visited nodes.

This heuristic created by Professor Nicos Christofides.

See also: http://ocw.mit.edu/NR/rdonlyres/Civil-and-Environmental-Engineering/1-203JFall-2004/66F3B435-07C9-465A-9A53-820E3E8943C0/0/nlec2.pdf