论文标题
改进了对欧几里得TSP的2-OPT的平滑分析
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
论文作者
论文摘要
2-OPT启发式是针对旅行销售人员问题（TSP）的一个简单的本地搜索启发式搜索。尽管通常在实践中表现良好，但最差的运行时间很差。试图调和这种差异的尝试使用了平滑的分析，其中对抗性实例概率受到干扰。我们对欧几里得TSP平滑分析的经典模型感兴趣，在该模型中，扰动是高斯。该模型以前是由曼斯（Manthey）\＆veenstra使用的，他获得了平滑的复杂性界限，以$ n $，尺寸$ d $和扰动强度$σ^{ - 1} $。但是，他们的分析仅适用于$ d \ geq 4 $。 $ d \ leq 3 $的唯一先前分析是由Englert，Röglin\＆Vöcking进行的，他使用了不同的扰动模型，可以将其转化为高斯扰动。他们的模型在$ n $和$σ^{ - d} $中得出多项式的界限，以及$ d $中的超级指数。由于对于所有$ d $都产生多项式界限的高斯扰动没有直接分析，因此我们执行此缺失的分析。一路上，我们改善了欧几里得2-OPT的所有现有平滑复杂性界限。
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 poor. Attempts to reconcile this difference 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 \& Veenstra, who obtained smoothed complexity bounds polynomial in $n$, the dimension $d$, and the perturbation strength $σ^{-1}$. However, their analysis only works for $d \geq 4$. The only previous analysis for $d \leq 3$ was performed by Englert, Röglin \& Vöcking, who used a different perturbation model which can be translated to Gaussian perturbations. Their model yields bounds polynomial in $n$ and $σ^{-d}$, and super-exponential in $d$. As no direct analysis existed for Gaussian perturbations that yields polynomial bounds for all $d$, we perform this missing analysis. Along the way, we improve all existing smoothed complexity bounds for Euclidean 2-opt.
