Analysis of Solution Quality

This is the interesting part. How does the tour we find relate to the optimal tour?

Recall $\mbox{\rm OPT}$ is the length of the best tour, M is the size of the MST we found, and C is the length of the tour we return. Facts:

• $M \le \mbox{\rm OPT}$. Tour spans nodes. So, $2 M \le 2\; \mbox{\rm OPT}$
• $C \le 2 M$. Touring the tree is 2 M, shortcuts only make it smaller.
• Therefore, $C \le 2 \; \mbox{\rm OPT}$! (Ratio of 2.)

So, even though we don't know $\mbox{\rm OPT}$, we know it can't be too far away!