TR06-092 Authors: Matthias Englert, Heiko Röglin, Berthold Vöcking

Publication: 2nd August 2006 23:51

Downloads: 6006

Keywords:

2-Opt is probably the most basic and widely used 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 Euclidean instances was

known so far. In this paper, we clarify this issue by presenting a

family of Euclidean 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 according to general distributions on $[0,1]^2$. In

particular, we allow different distributions for different points.

We study the expected running time in terms of the number $n$ of

points and the maximal density $\phi$ 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^{3+5/6}\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^{3.5}\cdot\phi)$. In addition,

we prove an upper bound of $O(\sqrt{\phi})$ on the expected

approximation factor w.r.t. both of these metrics.

Let us remark that our probabilistic analysis covers as special

cases the uniform input model with $\phi=1$ and a smoothed analysis

with Gaussian perturbations of standard deviation $\sigma$ with

$\phi\sim 1/\sigma^2$. Besides random metric instances, we also

consider an alternative random input model in which an adversary

specifies a graph and distributions for the edge lengths in this

graph. In this model, we achieve even better results on the expected

running time of 2-Opt.