Trivial approximation ratio of n/2 for 2-Opt for TSPI recently read that the 2-Opt algorithm...
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
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 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 denote an optimal Tour. Let be an arbitrary edge of T. Note that is the disjoint union of two paths and where one is a v-w-Path and the other is a w-v-Path. By the triangle inequality we have and similarily . Together with it follows that Step 2 Therefore , 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.