Trivial approximation ratio of n/2 for 2-Opt for TSPI recently read that the 2-Opt algorithm...

Jovany Clayton

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)

Answer & Explanation

enfeinadag0

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 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 ) w ( P 1 ) = f E ( P 1 ) w ( f ) and similarily w ( e ) w ( P 2 ). Together with w ( T ) = f E ( T ) w ( f ) = w ( P 1 ) + w ( P 2 ) it follows that 2 w ( e ) w ( T ) .
Step 2
Therefore w ( T ) = e E ( T ) w ( e ) e E ( T ) 1 2 w ( T ) = 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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?