The Approximation Ratio of the 2 Opt Heuristic for the Metric Traveling Salesman Problem
The 2 Opt heuristic is one of the simplest algorithms for finding good solutions to the metric Traveling Salesman Problem. It is the key ingredient to the well known Lin Kernighan algorithm and often used in practice. So far, only upper and lower bounds on the approximation ratio of the 2 Opt heuristic for the metric TSP were known. We prove that for the metric TSP with $n$ cities, the approximation ratio of the 2 Opt heuristic is \sqrt{n/2} and that this bound is tight.
Oper. Res. Lett.