Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for Gaussian noise

Bodo Manthey, Rianne Veenstra

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)

Abstract

The 2-opt heuristic is a very simple local search heuristic for the traveling salesman problem. While it usually converges quickly in practice, its running-time can be exponential in the worst case. In order to explain the performance of 2-opt, Englert, Röglin, and Vöcking (Algorithmica, to appear) provided a smoothed analysis in the so-called one-step model on d-dimensional Euclidean instances. However, translating their results to the classical model of smoothed analysis, where points are perturbed by Gaussian distributions with standard deviation $\sigma$, yields a bound that is only polynomial in $n$ and $1/\sigma^d$. We prove bounds that are polynomial in $n$ and $1/\sigma$ for the smoothed running-time with Gaussian perturbations. In particular our analysis for Euclidean distances is much simpler than the existing smoothed analysis.
Original language Undefined Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013) Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam Berlin Springer 579-589 11 978-3-642-45029-7 https://doi.org/10.1007/978-3-642-45030-3_54 Published - 2013 24th International Symposium on Algorithms and Computation (ISAAC 2013), Hong Kong, China: Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013) - BerlinDuration: 1 Jan 2013 → …

Publication series

Name Lecture Notes in Computer Science Springer Verlag 8283 0302-9743 1611-3349

Conference

Conference 24th International Symposium on Algorithms and Computation (ISAAC 2013), Hong Kong, China Berlin 1/01/13 → …

• EWI-23603
• METIS-299988
• IR-88245