The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of optimality. In contrast to this, its running-time is exponential and its approximation performance is poor in the worst case. Englert, Röglin, and Vöcking (Algorithmica, 2014) provided a smoothed analysis in the so-called one-step model in order to explain the performance of 2-opt on d-dimensional Euclidean instances, both in terms of running-time and in terms of approximation ratio. However, translating their results to the classical model of smoothed analysis, where points are perturbed by Gaussian distributions with standard deviation <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1335_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(\sigma \)</EquationSource> </InlineEquation>, yields only weak bounds. We prove bounds that are polynomial in n and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1335_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="29" /> </InlineMediaObject> <EquationSource Format="TEX">\(1/\sigma \)</EquationSource> </InlineEquation> for the smoothed running-time with Gaussian perturbations. In addition, our analysis for Euclidean distances is much simpler than the existing smoothed analysis. Furthermore, we prove a smoothed approximation ratio of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1335_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="86" /> </InlineMediaObject> <EquationSource Format="TEX">\(O(\log (1/\sigma ))\)</EquationSource> </InlineEquation>. This bound is almost tight, as we also provide a lower bound of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1335_Article_IEq4.gif" Format="GIF" Height="26" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Omega (\frac{\log n}{\log \log n})\)</EquationSource> </InlineEquation> for <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1335_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="100" /> </InlineMediaObject> <EquationSource Format="TEX">\(\sigma = O(1/\sqrt{n})\)</EquationSource> </InlineEquation>. Our main technical novelty here is that, different from existing smoothed analyses, we do not separately analyze objective values of the global and local optimum on all inputs (which only allows for a bound of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1335_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">\(O(1/\sigma )\)</EquationSource> </InlineEquation>), but simultaneously bound them on the same input.

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

期刊论文
出版模式：

开放获取
发表日期：

2025年7月21日

查看全文

Marvin Künnemann,
Bodo Manthey,
Rianne Veenstra

摘要

The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of optimality. In contrast to this, its running-time is exponential and its approximation performance is poor in the worst case. Englert, Röglin, and Vöcking (Algorithmica, 2014) provided a smoothed analysis in the so-called one-step model in order to explain the performance of 2-opt on d-dimensional Euclidean instances, both in terms of running-time and in terms of approximation ratio. However, translating their results to the classical model of smoothed analysis, where points are perturbed by Gaussian distributions with standard deviation \(\sigma \) , yields only weak bounds. We prove bounds that are polynomial in n and \(1/\sigma \) for the smoothed running-time with Gaussian perturbations. In addition, our analysis for Euclidean distances is much simpler than the existing smoothed analysis. Furthermore, we prove a smoothed approximation ratio of \(O(\log (1/\sigma ))\) . This bound is almost tight, as we also provide a lower bound of \(\Omega (\frac{\log n}{\log \log n})\) for \(\sigma = O(1/\sqrt{n})\) . Our main technical novelty here is that, different from existing smoothed analyses, we do not separately analyze objective values of the global and local optimum on all inputs (which only allows for a bound of \(O(1/\sigma )\) ), but simultaneously bound them on the same input.