Approximation Idea

We want an efficient algorithm, just like we've had all along.

Ok, such an algorithm won't be able to find the best tour, but maybe we can guarantee ourselves to find something that's close to being optimal.

Idea: Let's say the cost of the truly optimal tour is $\mbox{\rm OPT}$, but we find a tour of length C. The ratio $C/\mbox{\rm OPT}\ge 1$ tells us how close we are to being optimal (the closer to 1, the better).

We'll give a fast algorithm that produces tours for metric TSP with a worst-case ratio of 2. So, we're never further than a factor of 2 away from optimal!