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)
10
-
$\begingroup$ I am not sure I understand your last note. Are you simply looking for a description of the 2-approximation algorithm for metric TSP? In that case you could start here: geeksforgeeks.org/…. Or are you wondering whether there is a 2-approximation algorithm for (general) TSP? Note that the answer is no unless $P = NP$. Let me know if you need more details or pointers. $\endgroup$– sebastianCommented Nov 17, 2021 at 16:54
-
$\begingroup$ @araomis Neither is the case and I am familiar with these. My last note is to clarify that one might need to assume that the distances form a metric to prove the ratio of $n/2$ easily. Since I do not know how to obtain such bound yet, I also don't know if the case with metric TSP simplifies the proof. Does this clarify what I meant? $\endgroup$– mc.mathCommented Nov 17, 2021 at 17:08
-
$\begingroup$ So the 2-Opt algorithm yields an approximation ratio of $2$, right? So if $n \geq 4$ you get $n/2 \geq 2$ and hence the same algorithm gives you an approximation ratio of $n/2$. If $n < 4$ you can brute-force an optimal solution. What am I missing here? $\endgroup$– sebastianCommented Nov 17, 2021 at 17:13
-
$\begingroup$ @araomis The 2-Opt algorithm does not yield an approximation ratio of 2. In fact, it does not even yield a constant approximation ratio (even for metric TSP). $\endgroup$– mc.mathCommented Nov 17, 2021 at 17:17
-
$\begingroup$ What is your definition of approximation ratio? $\endgroup$– sebastianCommented Nov 17, 2021 at 17:21
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
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.