Jovany Clayton

2022-07-02

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)

Expert

Step 1
For all those that stumble upon this question: The answer actually is quite simple. Let me explain.
Given an Instance $I=\left({K}_{n},w\right)$ of metric TSP, consider the following algorithm:
1. Construct an arbitrary Tour T through V.
2. Return T.
I claim that this simple algorithm already achieves an approximation ratio of n/2: Let ${T}^{\ast }$ denote an optimal Tour. Let $e=\left(v,w\right)$ be an arbitrary edge of T. Note that ${T}^{\ast }$ 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\left(e\right)\le w\left({P}_{1}\right)=\sum _{f\in E\left({P}_{1}\right)}w\left(f\right)$ and similarily $w\left(e\right)\le w\left({P}_{2}\right)$. Together with $w\left({T}^{\ast }\right)=\sum _{f\in E\left({T}^{\ast }\right)}w\left(f\right)=w\left({P}_{1}\right)+w\left({P}_{2}\right)$ it follows that $2w\left(e\right)\le w\left({T}^{\ast }\right).$
Step 2
Therefore $w\left(T\right)=\sum _{e\in E\left(T\right)}w\left(e\right)\le \sum _{e\in E\left(T\right)}\frac{1}{2}w\left({T}^{\ast }\right)=\frac{n}{2}w\left({T}^{\ast }\right),$, 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.

Do you have a similar question?