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

Bodo Manthey; Rianne Veenstra

doi:10.1007/978-3-642-45030-3_54

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 proceeding › Conference contribution › Academic › peer-review

17 Citations (Scopus)

92 Downloads (Pure)

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	English
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
Publisher	Springer
Pages	579-589
Number of pages	11
ISBN (Print)	978-3-642-45029-7
DOIs	https://doi.org/10.1007/978-3-642-45030-3_54
Publication status	Published - 2013
Event	24th International Symposium on Algorithms and Computation (ISAAC 2013), Hong Kong, China: Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013) - Berlin Duration: 1 Jan 2013 → …

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	8283
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

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

Access to Document

10.1007/978-3-642-45030-3_54

Complete, corrected version joining ISAAC 2013 and ICALP 2015Other version, 664 KB

17 Citations
1 Preprint

Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise
Künnemann, M., Manthey, B. & Veenstra, R., 1 Aug 2023, ArXiv.org.
Research output: Working paper › Preprint › Academic

Open Access
File
31 Downloads (Pure)

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). Springer. https://doi.org/10.1007/978-3-642-45030-3_54

@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 \$\textbackslash{}sigma\$, yields a bound that is only polynomial in \$n\$ and \$1/\textbackslash{}sigma\textasciicircum{}d\$. We prove bounds that are polynomial in \$n\$ and \$1/\textbackslash{}sigma\$ for the smoothed running-time with Gaussian perturbations. In particular our analysis for Euclidean distances is much simpler than the existing smoothed analysis.",

author = "Bodo Manthey and Rianne Veenstra",

note = "10.1007/978-3-642-45030-3\_54 ; 24th International Symposium on Algorithms and Computation (ISAAC 2013), Hong Kong, China : Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013) ; Conference date: 01-01-2013",

year = "2013",

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

language = "English",

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 = "Germany",

}

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). Lecture Notes in Computer Science, vol. 8283, Springer, Berlin, pp. 579-589, 24th International Symposium on Algorithms and Computation (ISAAC 2013), Hong Kong, China, Berlin, 1/01/13. https://doi.org/10.1007/978-3-642-45030-3_54

Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for Gaussian noise. / Manthey, Bodo; Veenstra, Rianne.
Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013). ed. / Leizhen Cai; Siu-Wing Cheng; Tak-Wah Lam. Berlin: Springer, 2013. p. 579-589 (Lecture Notes in Computer Science; Vol. 8283).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Manthey, Bodo

AU - Veenstra, Rianne

N1 - 10.1007/978-3-642-45030-3_54

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-45030-3_54

DO - 10.1007/978-3-642-45030-3_54

M3 - Conference contribution

SN - 978-3-642-45029-7

T3 - Lecture Notes in Computer Science

SP - 579

EP - 589

BT - Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013)

A2 - Cai, Leizhen

A2 - Cheng, Siu-Wing

A2 - Lam, Tak-Wah

PB - Springer

CY - Berlin

T2 - 24th International Symposium on Algorithms and Computation (ISAAC 2013), Hong Kong, China

Y2 - 1 January 2013

ER -

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Research output

Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise

Cite this