@inproceedings{3986e3fa37734b43b67a789c43c2bcbc,

title = "Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for Gaussian noise",

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{\"o}glin, and V{\"o}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.",

keywords = "EWI-23603, METIS-299988, IR-88245",

author = "Bodo Manthey and Rianne Veenstra",

note = "10.1007/978-3-642-45030-3_54 ; null ; Conference date: 01-01-2013",

year = "2013",

doi = "10.1007/978-3-642-45030-3_54",

language = "Undefined",

isbn = "978-3-642-45029-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "579--589",

editor = "Leizhen Cai and Siu-Wing Cheng and Tak-Wah Lam",

booktitle = "Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013)",

address = "Netherlands",

}