Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
verfasst von : Bodo Manthey, Rianne Veenstra
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
σ
, yields a bound that is only polynomial in
n
and 1/
σ
d
.
We prove bounds that are polynomial in
n
and 1/
σ
for the smoothed running-time with Gaussian perturbations. In particular our analysis for Euclidean distances is much simpler than the existing smoothed analysis.