We show that the problem of counting 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is O(1.2098n√n!). Based on numerical experiments, we conjecture that the true bound is at most O(√n!), which is approximately the square root of the total number of tours.

Abstract 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 ≥ 4 . The only previous analysis for $$d \le 3$$ d ≤ 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.

We analyze variants of the 2-opt local search heuristic for the Traveling Salesperson Problem (TSP) with guaranteed polynomial running-time. First we consider X-opt, a heuristic that removes intersecting pairs of edges from two-dimensional Euclidean instances. We show that the longest X-optimal tour may be approximately n / 2 times longer than the optimal tour in the worst case. Moreover, even when the instance consists of n points placed uniformly at random in the unit square, the longest tour is Ω ( n ) times longer than the optimal tour. Next, we propose a new heuristic, which we call Y-opt, that is defined for all TSP instances, not just Euclidean ones. Y-opt has essentially the same approximation guarantees as the well-studied 2-opt. We furthermore evaluate the approximation performance of both X-opt and Y-opt numerically on random instances and compare them to 2-opt. While Y-opt behaves as predicted, we find that X-opt appears to have a constant approximation ratio on these instances in practice.

We show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-complete. First, we show that the Hartigan--Wong method for $k$-Means clustering is PLS-complete, even when $k = 2$. Second, we show the same result for the Flip heuristic for Max Cut, even when the edge weights are given by the (squared) Euclidean distances between the points in some set $\mathcal{X} \subseteq \mathbb{R}^d$; a problem which is equivalent to Min Sum 2-Clustering.

We analyze the running time of the Hartigan-Wong method, an old algorithm for the $k$-means clustering problem. First, we construct an instance on the line on which the method can take $2^{Ω(n)}$ steps to converge, demonstrating that the Hartigan-Wong method has exponential worst-case running time even when $k$-means is easy to solve. As this is in contrast to the empirical performance of the algorithm, we also analyze the running time in the framework of smoothed analysis. In particular, given an instance of $n$ points in $d$ dimensions, we prove that the expected number of iterations needed for the Hartigan-Wong method to terminate is bounded by $k^{12kd}\cdot poly(n, k, d, 1/σ)$ when the points in the instance are perturbed by independent $d$-dimensional Gaussian random variables of mean $0$ and standard deviation $σ$.

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 ≥ 4. The only previous analysis for d ≤ 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 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.