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.
|Title of host publication||Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013)|
|Editors||Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam|
|Place of Publication||Berlin|
|Number of pages||11|
|Publication status||Published - 2013|
|Name||Lecture Notes in Computer Science|
Manthey, B., & Veenstra, R. (2013). Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for Gaussian noise. In L. Cai, S-W. Cheng, & T-W. Lam (Eds.), Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013) (pp. 579-589). (Lecture Notes in Computer Science; Vol. 8283). Berlin: Springer. https://doi.org/10.1007/978-3-642-45030-3_54