### 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 |
---|---|

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

Publication status | Published - 2013 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 8283 |

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