Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

Matthias Englert, Heiko Röglin, Berthold VöckingAlgorithmica 2014 · OpenReview

Abstract

2-Opt is probably the most basic local search heuristic for the Traveling Salesperson Problem (TSP). This heuristic achieves amazingly good results on “real world” Euclidean instances both with respect to running time and approximation ratio. However, the theoretical knowledge about this heuristic is still very limited. We clarify this issue by presenting a family of $L_p$ instances on which 2-Opt can take an exponential number of steps. We also consider a more advanced model of probabilistic instances in which the points can be placed independently according to general distributions. We show an upper bound on the expected length of any 2-Opt improvement path of $\tilde{O}(n^{4+1/3}\cdot\phi^{8/3})$. Our probabilistic analysis covers as special cases the uniform input model and a smoothed analysis with Gaussian perturbations.

Introduction

The Traveling Salesperson Problem (TSP) is a fundamental NP-hard optimization problem. The 2-Opt algorithm, a simple local search heuristic that iteratively swaps two edges to shorten the tour, is widely used due to its empirical efficiency. Despite its practical success, a significant gap has existed between its observed performance and theoretical guarantees. Specifically, while 2-Opt was known to have exponential worst-case performance on general graphs, its behavior on Euclidean instances remained an open question. Furthermore, previous probabilistic analyses provided overly pessimistic bounds (e.g., $O(n^{10})$) that did not align with real-world observations.

Worst-Case Construction in 2D

This work settles the question of 2-Opt's worst-case performance in Euclidean space. We construct a family of 2D instances for both Euclidean and Manhattan metrics where 2-Opt is forced to take an exponential number of steps. This is achieved through the design of "gadgets"—clusters of points that function as bits in a binary counter.

The construction of a family of instances $G_m$ where 2-Opt takes exponential time. The instance consists of gadgets $G_i$, each containing blocks $\mathcal{B}_1^i$ and $\mathcal{B}_2^i$.

The construction uses these gadgets to simulate an odometer. A local improvement in a "low-order" gadget triggers a cascade of resets in "higher-order" gadgets. For any $L_p$ metric in 2D, we demonstrate an instance with $16n$ vertices where 2-Opt requires $2^{n+4} - 22$ steps to reach a local optimum.

The sequence of states (L for long, S for short) for the blocks in the exponential construction, illustrating the binary counter behavior.

Probabilistic and Smoothed Analysis

To reconcile the exponential worst-case with practical efficiency, we employ a smoothed analysis framework. We assume each point $v_i$ is placed according to a probability density function $f_i$ with a maximum density $\phi$. This model accounts for the inherent "noise" in real-world data, which prevents the precise alignment required for the exponential counter gadgets to function.

Our analysis focuses on linked pairs of 2-Opt steps, proving that it is highly unlikely for consecutive, overlapping swaps to both yield negligible improvements. Key results include:

  • Manhattan Metric: The expected runtime is $O(n^4 \cdot \phi)$. When initialized with an insertion heuristic, this improves to $O(n^{4-1/d} \cdot \log n \cdot \phi)$.
  • Euclidean Metric: The expected runtime is $\tilde{O}(n^{4+1/3} \cdot \phi^{8/3})$.
  • Approximation Ratio: The expected approximation ratio is bounded by $O(\sqrt[d]{\phi})$, implying that for uniform distributions ($\phi=1$), 2-Opt is expected to find a solution within a constant factor of the optimum.

Conclusion

This research provides the first rigorous theoretical explanation for the practical success of 2-Opt. While geometry alone does not prevent exponential runtimes, even minimal randomness in point placement ensures polynomial expected time. Future work may explore whether finding a 2-Opt local optimum is PLS-complete for Euclidean instances and extend these techniques to more sophisticated heuristics like Lin-Kernighan.

Summary updated

Abstract

2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world” Euclidean instances both with respect to running time and approximation ratio. There are numerous experimental studies on the performance of 2-Opt. However, the theoretical knowledge about this heuristic is still very limited. Not even its worst case running time on 2-dimensional Euclidean instances was known so far. We clarify this issue by presenting, for every $p\in\mathbb{N}$ , a family of L p instances on which 2-Opt can take an exponential number of steps.Previous probabilistic analyses were restricted to instances in which n points are placed uniformly at random in the unit square [0,1]2, where it was shown that the expected number of steps is bounded by $\tilde{O}(n^{10})$ for Euclidean instances. We consider a more advanced model of probabilistic instances in which the points can be placed independently according to general distributions on [0,1] d , for an arbitrary d≥2. In particular, we allow different distributions for different points. We study the expected number of local improvements in terms of the number n of points and the maximal density ϕ of the probability distributions. We show an upper bound on the expected length of any 2-Opt improvement path of $\tilde{O}(n^{4+1/3}\cdot\phi^{8/3})$ . When starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to $\tilde{O}(n^{4+1/3-1/d}\cdot\phi^{8/3})$ . If the distances are measured according to the Manhattan metric, then the expected number of steps is bounded by $\tilde{O}(n^{4-1/d}\cdot\phi)$ . In addition, we prove an upper bound of $O(\sqrt[d]{\phi})$ on the expected approximation factor with respect to all L p metrics.Let us remark that our probabilistic analysis covers as special cases the uniform input model with ϕ=1 and a smoothed analysis with Gaussian perturbations of standard deviation σ with ϕ∼1/σ d .
BibTeX
@inproceedings{englert2014worst,
  author = {Matthias Englert and Heiko Röglin and Berthold Vöcking},
  title = {{Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP}},
  booktitle = {Algorithmica},
  year = {2014},
  url = {https://openreview.net/forum?id=1cKrQBPMSv1p},
}
Figure