1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ How do you know it is a $2$-approximation? What is the motivation for the question? $\endgroup$
    – Chandra Chekuri
    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$
    – Ioana Roman
    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$
    – Chandra Chekuri
    May 19, 2022 at 23:01

0

Reset to default

Your Answer

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