2-approximation algorithm for TravelingSalesmanTour? in metric graph:

#### References:

- Compute a minimum spanning tree (MST) T.
- Double every edge of T to to obtain an Eulerian graph.
- Find an Eulerian tour T' on this graph.
- Output the TST formed by visiting each vertex in order of its occurrence in T'.

**thm (thm 3.8 in text):*** The above algorithm is a 2-approximation algorithm.*

1.5-approximation algorithm for TST in metric graph

- Compute a minimum spanning tree T.
- Compute a minimum-cost perfect matching M on the odd-degree vertices of T.
- Add M to T to get an Eulerian graph.
- Find an Eulerian tour T' on this graph.
- Output the TST formed by visiting each vertex in order of its occurrence in T'.

**thm (Euler):*** Given an Eulerian graph, an Eulerian tour can be found in polynomial time.*

**thm (shortcutting):*** Given an Eulerian tour T in a metric graph, a Traveling Salesman Tour (TST) T' such that cost(T') ≤ cost(T) can be found in polynomial time.*

**thm:*** Given an even-sized subset S of vertices of a metric graph, the cost of the minimum-cost perfect matching on S is at most 1/2 the cost of the minimum cost TST.*

**corollary (thm 3.12 in text):**
* The above algorithm is a 1.5-approximation algorithm.*

- Chapter 3 of Approximation Algorithms by Vijay Vazirani.
- NIST entry for [Christofides' algorithm]