Jovany Clayton

Answered

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)

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)

Answer & Explanation

enfeinadag0

Expert

2022-07-03Added 16 answers

Step 1

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:

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=(v,w)$ 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(e)\le w({P}_{1})=\sum _{f\in E({P}_{1})}w(f)$ and similarily $w(e)\le w({P}_{2})$. Together with $w({T}^{\ast})=\sum _{f\in E({T}^{\ast})}w(f)=w({P}_{1})+w({P}_{2})$ it follows that $2w(e)\le w({T}^{\ast}).$

Step 2

Therefore $w(T)=\sum _{e\in E(T)}w(e)\le \sum _{e\in E(T)}\frac{1}{2}w({T}^{\ast})=\frac{n}{2}w({T}^{\ast}),$, 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.

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:

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=(v,w)$ 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(e)\le w({P}_{1})=\sum _{f\in E({P}_{1})}w(f)$ and similarily $w(e)\le w({P}_{2})$. Together with $w({T}^{\ast})=\sum _{f\in E({T}^{\ast})}w(f)=w({P}_{1})+w({P}_{2})$ it follows that $2w(e)\le w({T}^{\ast}).$

Step 2

Therefore $w(T)=\sum _{e\in E(T)}w(e)\le \sum _{e\in E(T)}\frac{1}{2}w({T}^{\ast})=\frac{n}{2}w({T}^{\ast}),$, 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.

Most Popular Questions