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.

  • $\begingroup$ How do you know it is a $2$-approximation? What is the motivation for the question? $\endgroup$ May 19, 2022 at 21:47
  • $\begingroup$ @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. $\endgroup$ May 19, 2022 at 22:04
  • 1
    $\begingroup$ 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. $\endgroup$ May 19, 2022 at 23:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.