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).  ] 
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.
R
euclidean
Euclidean
A
This improves the upper bound of O(\log n) given by Chandra, Karloff, and Tovey
A
3
A
in 1999.