PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Matthias Englert, Heiko Röglin, Berthold Vöcking

arXiv:2302.06889v1cs.DS

TL;DR

The paper addresses limited theoretical understanding of 2-Opt by analyzing both worst-case behavior and probabilistic input models. It constructs exponentially long improvement paths and derives expected-step and approximation-ratio bounds under general density-bounded distributions.

  • Problem

    Worst-case analysis had not explained 2-Opt’s practical performance, and prior negative results left the existence of exponential paths in the Euclidean plane unresolved.

  • Method

    The paper constructs local gadget-based instances for all L_p metrics and analyzes independently sampled points from potentially different density-bounded distributions in [0,1]^d.

  • Results

    A two-dimensional L_p instance with 16n vertices has a 2-Opt state-graph path of length 2^(n+4)−22, while expected-step bounds include O(n^(4+1/3)·log(nφ)·φ^(8/3)) for φ-perturbed Euclidean instances.

  • Takeaways & Limitations

    2-Opt can require exponentially many improving steps under particular pivot rules, while its expected behavior admits density- and dimension-dependent upper bounds.

  • Takeaways & Limitations

    The lower bounds apply only to particular pivot rules, and the probabilistic bounds may be too pessimistic because the analysis focuses solely on the smallest improvement in linked 2-changes.

Abstract

from arXiv · show

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$. We consider a more advanced model in which the points can be placed independently according to general distributions on $[0,1]^d$, for an arbitrary $d\ge 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φ^{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φ^{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φ)$. In addition, we prove an upper bound of $O(\sqrt[d]φ)$ 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 $φ\sim1/σ^d$.

1. Introduction

The paper addresses the limited theoretical understanding of 2-Opt by proving exponential worst-case paths and developing probabilistic bounds for independently distributed points with bounded density. It also analyzes approximation ratios across Lp metrics and shows improved step bounds for insertion-based initialization.

  • 2-Opt and motivation: 2-Opt repeatedly exchanges two tour edges for two others when the replacement decreases tour length, terminating at a locally optimal tour.A local improvement is called a 2-change.
  • Worst-case analysis: 2^(n+4)−22 steps are possible in a two-dimensional Lp instance with 16n vertices, for every p∈{1,2,3,...}∪{∞}.The construction establishes exponential-length paths in the 2-Opt state graph.
  • Probabilistic model: The probabilistic model independently places vertices according to possibly different densities bounded by φ on [0,1]^d, generalizing the uniform model.The dimension d is at least 2, and φ=1 with d=2 recovers uniform points in the unit square.
  • Probabilistic bounds: O(n^(4+1/3)·log(nφ)·φ^(8/3)) bounds the expected longest 2-Opt path for φ-perturbed Euclidean instances.This applies to arbitrary initial tours in the stated Euclidean probabilistic model.
  • Probabilistic bounds: O(n^(4−1/d)·log n·φ) bounds expected steps for φ-perturbed Manhattan instances with insertion-heuristic initialization.For Manhattan instances, the analysis also polynomially bounds the second moment and variance; for Euclidean instances, it bounds the 3/2-th moment instead.
  • Probabilistic bounds: O(n^(4+1/3−1/d)·log^2(nφ)·φ^(8/3)) bounds expected steps for Euclidean instances initialized by an arbitrary insertion heuristic.The improvement is attributed to the shorter initial tour produced by insertion heuristics.
  • Approximation quality: The expected approximation ratio of the worst 2-Opt local optimum is O(φ^(1/d)) for φ-perturbed Lp instances.This generalizes the constant expected bound known for uniformly random points in the unit square.

2. Preliminaries

The preliminaries define TSP instances, metric spaces, Lp distances, tours, and insertion heuristics. These definitions establish the terminology and input constructions used in the paper’s analyses.

  • TSP definitions: A TSP instance consists of vertices and a symmetric distance function, with the goal of finding a minimum-length Hamiltonian cycle.A Hamiltonian cycle is also called a tour.
  • Metric spaces: A metric space requires distances to satisfy reflexivity, symmetry, and the triangle inequality.Metric TSP instances use a distance function forming such a metric space.
  • Lp metrics: For finite p, the Lp distance combines coordinatewise absolute differences raised to p; L1 is Manhattan and L2 is Euclidean.As p approaches infinity, the metric becomes the maximum coordinate difference, defining L∞.
  • Tour construction: An insertion heuristic builds a tour incrementally by inserting each vertex between consecutive tour vertices where it fits best.Such heuristics commonly provide the initial tour for 2-Opt.
  • Tour construction: Nearest insertion and cheapest insertion achieve approximation ratio 2 on metric TSP instances, while arbitrary insertion heuristics have an upper bound of ⌈log n⌉+1.Nearest insertion selects the vertex closest to the current tour; cheapest insertion selects the best insertion position.

3. Exponential Lower Bounds

The paper constructs Euclidean and general L_p TSP instances where 2-Opt follows exponentially long sequences of improving 2-changes. Constant-size gadgets encode states and recursively reset one another, yielding exponential paths while preserving local interactions.

  • 3. Exponential Lower Bounds: Starting with G0 in zero state and all later gadgets in one state, gadget Gi changes from zero to one 2^i times.Recursive resets therefore produce a path of length 2^(n+3−i)−14 for the relevant suffix of gadgets.
  • 3. Exponential Lower Bounds: Each gadget consists of two four-vertex blocks, with zero state (L, L), one state (S, S), and intermediate state (S, L).Only these three of the four possible block-state combinations occur in the constructed sequence.
  • 3. Exponential Lower Bounds: A seven-2-change transition advances one gadget while resetting its neighboring gadget from one state to zero.The transition affects only edges within and between two adjacent gadgets.
  • 3. Exponential Lower Bounds: The Euclidean embedding makes every 2-change improving by exploiting scaled, rotated, and translated copies of gadget pairs.The proof reduces the required inequalities to the reset sequence for the final two gadgets.
  • 3. Exponential Lower Bounds: For Manhattan distance, alternating propagation and reset gadgets relax the reset requirement and still yield an exponential improving sequence; the construction also extends to L∞ and integer L_p metrics.The Manhattan construction uses 2n gadgets, with propagation gadgets resetting neighbors once and reset gadgets following the Euclidean behavior.

4. Expected Number of 2-Changes

The analysis bounds expected 2-Opt improvements by exploiting randomness in φ-perturbed instances, while accounting for dependencies specific to Manhattan and Euclidean metrics.

  • The analysis studies expected 2-changes on random d-dimensional Manhattan and Euclidean instances for arbitrary constant d ≥2.
  • A smallest-improvement analysis gives polynomial bounds, but the paper instead analyzes longer sequences of improvements.
  • General φ-perturbed graphs permit sequences of length √log m because their edge lengths are independent random variables.
  • For Manhattan and Euclidean instances, dependencies among edge lengths limit the benefit of analyzing longer improvement sequences.

4.1. Manhattan Instances

The Manhattan-instance analysis first derives a weaker bound from the smallest improving step, then improves it by grouping linked pairs of 2-changes and bounding their joint small-improvement probability.

  • Weaker bound: O(n^6 · log n · φ) bounds the expected number of 2-Opt steps from an arbitrary tour when vertex coordinates are drawn independently.The proof uses an upper bound on the initial tour length and a union bound showing that improving steps are unlikely to be extremely small.
  • Weaker bound: At most n^4 possible 2-Opt steps and the bound T ≤ n! convert a lower-tail estimate for the smallest improvement into an expected-step bound.If T exceeds t, the smallest improvement must be less than dn/t; the finite number of tours controls the remaining tail.
  • Linked-pair refinement: The smallest-step analysis is pessimistic because consecutive improvements can be paired, producing a combined improvement involving the smallest and second-smallest steps.The analysis therefore regroups steps into linked pairs rather than treating every improvement independently.
  • Linked-pair refinement: At least (2t − n)/7 disjoint linked pairs occur in every sequence of t consecutive 2-changes.The construction processes consecutive changes into linked pairs and removes overlaps; each retained pair conflicts with at most six others.
  • Pair types: O(n^6 · ε^2 · φ^2) bounds the probability that a type 0 or type 1 pair contains two improvements of size at most ε.The estimate follows by bounding each tuple’s probability by (εφ)^2 and applying a union bound over O(n^6) possibilities.

4.2. Euclidean Instances

The Euclidean analysis bounds small 2-Opt improvements by studying random variables describing individual and linked 2-changes. These probability bounds yield expected running-time bounds for arbitrary initial tours and improved bounds for insertion-generated tours.

  • The analysis replaces the Manhattan-specific lemma with an L2 version for φ-perturbed Euclidean instances.The authors note that the Euclidean bound is slightly weaker, leading to a slightly worse expected running-time bound than for L1.
  • Lemma 14 bounds the probability of two linked improvements by O(n6 · φ5 · ε2 · log2(1/ε)) + O(n5 · φ4 · ε3/2 · log(1/ε)).The bound applies to pairs of type 0 or type 1 whose two improvements are at most ε ≤ 1/2.
  • The improvement of a 2-change is expressed as Δ = Z1 − Z2, where Zi is a difference between distances from O and P to Qi.Conditioned on T, the variables Z1 and Z2 are identically distributed and independent.
  • For a single random point, Z = d(O, Q) − d(P, Q) has support [−τ, min{τ, 2r − τ}].The support restriction makes the conditional density zero outside this interval.
  • O(n7 · log2(n) · φ3) is the expected number of 2-Opt steps from an arbitrary initial tour on φ-perturbed Euclidean instances.The longer-path bound underlying this result is O(n4+1/3 · log(nφ) · φ8/3).
  • Θ(n1/d / log n) is the improvement factor obtained by estimating an insertion heuristic’s initial tour more tightly than O(n).This yields the bound stated in Theorem 3 b).

5. Expected Approximation Ratio

The approximation-ratio analysis partitions the unit hypercube and studies occupied cells under bounded, possibly nonidentical point densities. Concentration of occupied cells combines with geometric tour bounds to control the expected ratio of locally optimal solutions.

  • The analysis applies to φ-perturbed Lp instances and uses the fact that every locally optimal norm-induced tour has length O(n(d−1)/d).This prior geometric bound is combined with the probabilistic occupancy analysis.
  • The unit hypercube is partitioned into k equal-volume cells, and X counts the cells containing at least one point.The construction also selects separated points from occupied cells to lower-bound the optimal tour length.
  • Each point may have its own distribution over cells, while bounded density implies pij ≤ φ/k.This occupancy model is equivalent to throwing balls into bins with point-specific probability distributions.
  • E[X] ≥ n/2d+2, and the occupied-cell count is sharply concentrated around its mean.The variables Xi are shown to be negatively associated, allowing a Chernoff bound despite their dependence.
  • Combining occupancy concentration with the locally optimal-tour bound yields an expected approximation-ratio bound for all Lp metrics.The supplied proof passages state this combination but do not preserve the final displayed asymptotic expression.
  • The rare event X < n/2d+3 contributes only an exponentially small amount to the expected approximation ratio.On that event, the analysis uses n as an upper bound valid for any tour.

6. Smoothed Analysis

The paper interprets its bounded-density model as a smoothed analysis framework in which an adversary chooses point distributions before random perturbation. Gaussian perturbations fit the framework after controlling support and density.

  • Smoothed analysis is presented as a hybrid of worst-case and average-case analysis allowing adversarial input followed by random perturbation.Here, the adversary chooses distributions for points over the unit hypercube, subject to density restrictions.
  • Truncated Gaussian perturbations keep points in [−α, 1 + α]d and permit application of Theorems 2, 3, and 4 after rescaling.Rescaling and translating to [0, 1]d increases maximal density by at most (2α + 1)d.
  • For sufficiently small σ, untruncated Gaussian perturbations have failure probability at most n−n for leaving the permitted range.The bound follows from a union bound over all dn Gaussian variables.
  • Gaussian perturbations with standard deviation σ correspond to maximal density φ = O(αd/σd) after scaling.The density estimate is based on the truncated Gaussian density and the support transformation.
  • O(poly(n, 1/σ)) bounds the expected length of the longest 2-Opt state-graph path under the Gaussian perturbation treatment.Worst-case bounds and the exponentially small failure probability contribute less than 1 to the expected values.

7. Conclusions and Open Problems

The paper establishes new worst-case and probabilistic results for 2-Opt, while leaving major questions about pivot rules, computational complexity, and theory–experiment agreement open.

  • The paper reports new results on the running time and approximation ratio of 2-Opt.
  • The exponential lower bounds apply only to particular pivot rules, leaving the state-graph diameter and universal exponential behavior unresolved.
  • Worst-case improvement counts for natural pivot rules, including largest-improvement and random-improvement rules, remain unknown.
  • Whether computing a locally optimal Euclidean 2-Opt solution is PLS-complete remains open, despite hardness results for related settings.
  • The probabilistic bounds are considered too pessimistic to close the gap with experiments, and improving the approximation-ratio constant remains challenging.
  • Lin-Kernighan is a practically successful variable-k local-search heuristic whose theoretical behavior is comparatively underdeveloped.

A. Inequalities from Section 3.2.2

This appendix verifies the inequalities used in the construction through bounds for ranges of p and direct checks for the remaining small cases.

  • Remaining cases are handled by plugging in the appropriate integer values, including p ∈{3, 4}, p ∈{3, 4, 5, 6}, and p = 3.
  • For several inequalities, the proof bounds p-th-root expressions for sufficiently large p and shows a positive residual.
  • The inequalities are established separately for ranges such as p ≥3, p ≥5, and p ≥7 using explicit numerical comparisons.

B. Some Probability Theory

The probability-theory appendix bounds probabilities of linear constraints by changing variables to a basis containing those constraints and exploiting bounded, independent densities.

  • Lemma 20 considers independent d-dimensional random vectors with densities bounded by φ and k fixed linearly independent integer constraints.
  • A change of variables uses the constraint vectors together with canonical basis vectors, producing a bijection with an integer matrix.
  • Independence factorizes the original joint density, while the inverse-Jacobian determinant has absolute value at most one.
  • The transformed density is bounded by φ^k times the remaining coordinate densities, and integrating k intervals of length ε yields the corresponding ε^k factor.

C.1. Proof of Lemma 16

The proof of Lemma 16 represents the density of a difference as a convolution and derives upper bounds by splitting into cases according to τ, r1, r2, and δ.

  • The conditional density of ∆ is expressed as the convolution of the conditional densities of Z1 and Z2.
  • The proof distinguishes cases based on the relative order of τ, r1, and r2, restricting δ to ranges where the difference density can be nonzero.
  • Each case bounds the density of ∆ by estimating the Z1 and Z2 densities and evaluating integrals over intersections of their supports.
  • After applying substitutions and the preceding bounds, the case analyses yield upper bounds on the density of ∆ and together prove the lemma.

C.2. Proof of Lemma 17

The proof bounds conditional densities of the random variable ∆ by decomposing integrals according to the radii R1 and R2 relative to τ. It combines earlier density lemmas with Lemma 22 and integrates over τ to establish Lemma 17.

  • Conditional density bounds: The proof conditions on T = τ and either R1 = r1 or R2 = r2, then expresses the density of ∆ through integrals over the remaining radius.The cases are split according to whether each radius is below or above τ.
  • Geometric setup: The geometric setup uses radii R1 and R2 from uniformly sampled points in a d-dimensional hyperball, whose volume scales as Vd(r) = αr^d.The distribution function of R2 is therefore proportional to the hyperball volume.
  • Auxiliary integral bound: Lemma 22 bounds the relevant logarithmic integrals for linear functions with |a| ≥ 1.Its proof uses a substitution and symmetry and monotonicity of ln(1/|z|).
  • Conditional density bounds: The resulting conditional densities f∆|T=τ,R1=r1 and f∆|T=τ,R2=r2 are bounded above after applying Lemmas 16, 21, and 22.The proof treats separately the configurations r1 ≤ τ, τ ≤ r1, r2 ≤ τ, and τ ≤ r2.
  • Integration over T: Lemma 17 is proved by integrating the conditional density over all possible values of T, using fT for the density of T = d(O, P).The argument also uses the density of the radius R1 and bounds on the conditional density of Zi.

D. Negatively Associated Random Variables

This section establishes negative association for bin-occupancy indicators in a balls-into-bins process with independent balls and ball-specific bin distributions. The property then supports applying Chernoff-Hoeffding bounds to sums of these variables.

  • Definition: Negative association means that increasing or decreasing functions of disjoint variable sets have nonpositive correlation in expectation.The defining inequality compares the expectation of a product with the product of expectations.
  • Consequence: Chernoff-Hoeffding bounds apply to sums of negatively associated random variables.The section cites this result from Dubhashi and Ranjan for the later analysis.
  • Proof strategy: Applying coordinatewise non-decreasing functions to disjoint negatively associated variable sets preserves negative association.This closure rule converts per-ball indicators into bin-occupancy indicators.
  • Balls-into-bins process: Theorem 26 states that bin-occupancy indicators are negatively associated when balls are independently placed into bins with individual probability distributions.Each Xi indicates whether bin i contains at least one ball.
  • Proof strategy: The proof introduces per-ball, per-bin indicators and combines negative association across bins with independence across balls.The closure properties are supplied by Lemma 25 parts a) and b).
Loading 2302.06889v1…