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 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.
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