Trivial approximation ratio of $n/2$ for 2-Opt for TSP I recently read that the 2-Opt algorithm for the TSP yielded an approximation ratio of $n/2$ by trivial reasons. However, there was neither proof nor further context provided and I am curious how this bound can be obtained since I don't see these trivial reasons. I hope you can help me and give some intuition of why this ratio holds. (Note: Perhaps this can only obtained easily when considering metric TSP which would totally suffice for my concerns)
 A: For all those that stumble upon this question: The answer actually is quite simple. Let me explain.
Given an Instance $I = (K_n,w)$ of metric TSP, consider the following algorithm:

*

*Construct an arbitrary Tour $T$ through $V$.

*Return $T$.

I claim that this simple algorithm already achieves an approximation ratio of $n/2$: Let $T^*$ denote an optimal Tour. Let $e = (v,w)$ be an arbitrary edge of $T$. Note that $T^*$ is the disjoint union of two paths $P_1$ and $P_2$ where one is a $v$-$w$-Path and the other is a $w$-$v$-Path. By the triangle inequality we have
$$ w(e) \leq w(P_1) = \sum_{f \in E(P_1) } w(f)$$
and similarily $w(e) \leq w(P_2)$. Together with $w(T^*) = \sum_{f \in E(T^*)} w(f) = w(P_1) + w(P_2)$ it follows that
$$ 2w(e) \leq w(T^*).$$
Therefore
$$ w(T) = \sum_{e \in E(T)} w(e) \leq \sum_{e \in E(T)} \frac{1}{2}w(T^*) = \frac{n}{2}w(T^*),$$
which proves the claim.
My initial confusion came from the misunderstanding this approximation ratio would have something to do with the specific 2-Opt algorithm. However, as argued above, this is not the case and this approximation ratio is quite trivial to achieve.
