  We analyze a tour-uncrossing heuristic for the Travelling Salesperson
Problem, showing that its worst-case approximation ratio is $\Omega(n)$ and its
average-case approximation ratio is $\Omega(\sqrt{n})$ in expectation. We
furthermore evaluate the approximation performance of this heuristic
numerically on average-case instances, and find that it performs far better
than the average-case lower bound suggests. This indicates a shortcoming in the
approach we use for our analysis, which is a rather common approach in the
analysis of local search heuristics.
