  The 2-Opt heuristic is a simple improvement heuristic for the Traveling
Salesman Problem. It starts with an arbitrary tour and then repeatedly replaces
two edges of the tour by two other edges, as long as this yields a shorter
tour. We will prove that for Euclidean Traveling Salesman Problems with $n$
cities the approximation ratio of the 2-Opt heuristic is $\Theta(\log n/ \log
\log n)$. This improves the upper bound of $O(\log n$) given by Chandra,
Karloff, and Tovey [3] in 1999.
