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

9 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 languageUndefined
Title of host publicationProceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013)
EditorsLeizhen Cai, Siu-Wing Cheng, Tak-Wah Lam
Place of PublicationBerlin
PublisherSpringer
Pages579-589
Number of pages11
ISBN (Print)978-3-642-45029-7
DOIs
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume8283
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

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

Cite this

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