<p>Consider the <em>Cheapest Insertion</em> Algorithm on a complete graph with <span class="math-container">$n$</span> vertices, where each edge <span class="math-container">$uv$</span> has a weight <span class="math-container">$w(uv)$</span>, and the weights satisfy the triangle inequality <span class="math-container">$w(xz)\leq w(xy)+w(yz)$</span> for all <span class="math-container">$x,y,z$</span>:</p>
<p>Start with any vertex <span class="math-container">$v_1$</span>. Suppose at step <span class="math-container">$1\leq t \leq n$</span> we have a sequence of distinct vertices <span class="math-container">$s_t = (v_1, \dots, v_t)$</span>. Pick <span class="math-container">$1\leq i \leq t$</span> and <span class="math-container">$u \notin \{v_1,\dots,v_t\}$</span> to minimise <span class="math-container">$w(v_iu)$</span>. Define <span class="math-container">$s_{t+1}$</span> by inserting <span class="math-container">$u$</span> into <span class="math-container">$s_t$</span> after <span class="math-container">$v_i$</span>. Output the Hamiltonian cycle defined by <span class="math-container">$s_n$</span>.</p>
<p>I know that this is a <span class="math-container">$2$</span> approximation to the Metric Travelling Salesman Problem (TSP), but I am wondering how we could prove that this is actually the case.</p>

CC BY-SA 4.0
2022-05-19T21:47:43.770Z
How do you know it is a $2$-approximation? What is the motivation for the question?
Chandra Chekuri
CC BY-SA 4.0
2022-05-19T22:04:54.870Z
@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.
Ioana Roman
CC BY-SA 4.0
2022-05-19T23:01:56.653Z
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.
Chandra Chekuri
<graph-theory><graph-algorithms><complexity><tsp><hamiltonian-paths>
Cheapest Insertion is $2$-approximation for TSP
Ioana Roman
# Cheapest Insertion is $2$-approximation for TSP

(Asked by: username_0 on 2022-05-19)

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.

**Tags:** graph-theory, graph-algorithms, complexity, tsp, hamiltonian-paths

> **Comments:**
> **username_1**: How do you know it is a $2$-approximation? What is the motivation for the question?  
> **username_0**: @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.  
> **username_1**: 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.  

---

## 0 answers

