On the Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP

The 2-Opt heuristic is a simple, easy-to-implement local search heuristic for the traveling salesman problem. While it usually provides good approximations to the optimal tour in experiments, its worst-case performance is poor. In an attempt to explain the approximation performance of 2-Opt, we prove an upper bound of exp(O( log(1/σ))) for the smoothed approximation ratio of 2-Opt. As a lower bound, we prove that the worst-case lower bound of Ω ( lognlog logn) for the approximation ratio holds for σ = O(1/ n). Our main technical novelty is that, different from existing smoothed analyses, we do not separately analyze objective values of the global and the local optimum on all inputs, but simultaneously bound them on the same input. 1 2-Opt and Smoothed Analysis The traveling salesman problem (TSP) is one of the best-studied combinatorial optimization problems. Euclidean TSP is the following variant: given points X ⊆ [0, 1]d, find the shortes