The 2-opt heuristic is a simple local search heuristic for the travelling salesperson problem (TSP). Although it usually performs well in practice, its worst-case running time is exponential in the number of cities. Attempts to reconcile this difference between practice and theory have used smoothed analysis, in which adversarial instances are perturbed probabilistically. We are interested in the classical model of smoothed analysis for the Euclidean TSP, in which the perturbations are Gaussian. This model was previously used by Manthey and Veenstra, who obtained smoothed complexity bounds polynomial in n, the dimension d, and the perturbation strength <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1309_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="27" /> </InlineMediaObject> <EquationSource Format="TEX">$\sigma ^{-1}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>σ</mi> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> </math></EquationSource> </InlineEquation>. However, their analysis only works for <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1309_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$d \ge 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>. The only previous analysis for <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1309_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$d \le 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>≤</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> was performed by Englert, Röglin and Vöcking, who used a different perturbation model which can be translated to Gaussian perturbations. Their model yields bounds polynomial in n and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1309_Article_IEq4.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="29" /> </InlineMediaObject> <EquationSource Format="TEX">$\sigma ^{-d}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>σ</mi> <mrow> <mo>-</mo> <mi>d</mi> </mrow> </msup> </math></EquationSource> </InlineEquation>, and super-exponential in d. As the fact that no direct analysis exists for Gaussian perturbations that yields polynomial bounds for all d is somewhat unsatisfactory, we perform this missing analysis. Along the way, we improve all existing smoothed complexity bounds for Euclidean 2-opt with Gaussian perturbations.

Improved Smoothed Analysis of 2-Opt for the Euclidean TSP

期刊论文
出版模式：

开放获取
发表日期：

2025年4月10日

查看全文

Bodo Manthey,
Jesse van Rhijn

摘要

The 2-opt heuristic is a simple local search heuristic for the travelling salesperson problem (TSP). Although it usually performs well in practice, its worst-case running time is exponential in the number of cities. Attempts to reconcile this difference between practice and theory have used smoothed analysis, in which adversarial instances are perturbed probabilistically. We are interested in the classical model of smoothed analysis for the Euclidean TSP, in which the perturbations are Gaussian. This model was previously used by Manthey and Veenstra, who obtained smoothed complexity bounds polynomial in n, the dimension d, and the perturbation strength $\sigma ^{-1}$ $σ^{- 1}$ . However, their analysis only works for $d \ge 4$ $d \geq 4$ . The only previous analysis for $d \le 3$ $d \leq 3$ was performed by Englert, Röglin and Vöcking, who used a different perturbation model which can be translated to Gaussian perturbations. Their model yields bounds polynomial in n and $\sigma ^{-d}$ $σ^{- d}$ , and super-exponential in d. As the fact that no direct analysis exists for Gaussian perturbations that yields polynomial bounds for all d is somewhat unsatisfactory, we perform this missing analysis. Along the way, we improve all existing smoothed complexity bounds for Euclidean 2-opt with Gaussian perturbations.