# Cheapest Insertion is $2$-approximation for TSP

Consider the Cheapest Insertion Algorithm on a complete graph with $$n$$ vertices, where each edge $$uv$$ has a weight $$w(uv)$$, and the weights satisfy the triangle inequality $$w(xz)\leq w(xy)+w(yz)$$ for all $$x,y,z$$:

Start with any vertex $$v_1$$. Suppose at step $$1\leq t \leq n$$ we have a sequence of distinct vertices $$s_t = (v_1, \dots, v_t)$$. Pick $$1\leq i \leq t$$ and $$u \notin \{v_1,\dots,v_t\}$$ to minimise $$w(v_iu)$$. Define $$s_{t+1}$$ by inserting $$u$$ into $$s_t$$ after $$v_i$$. Output the Hamiltonian cycle defined by $$s_n$$.

I know that this is a $$2$$ approximation to the Metric Travelling Salesman Problem (TSP), but I am wondering how we could prove that this is actually the case.

• How do you know it is a $2$-approximation? What is the motivation for the question? May 19 at 21:47
• @ChandraChekuri I have seen a few papers online stating that this is a $2$-approximation, but no proof was included so I couldn't see why this is the case and I haven't managed to prove it yet. May 19 at 22:04
• You may be aware of the MST heuristic that gives a 2-approximation. You can try to see if the algorithm can be viewed as implementing the MST heuristic. May 19 at 23:01