THE APPROXIMATION RATIO OF THE k-OPT HEURISTIC FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM

The k-Opt heuristic is a simple improvement heuristic for the traveling salesman prob-lem. It starts with an arbitrary tour and then repeatedly replaces k edges of the tour by k other edges, as long as this yields a shorter tour. We will prove that for the 2-dimensional Euclidean traveling salesman problem with n cities the approximation ratio of the k-Opt heuristic is theta(log n/ log log n). This improves the upper bound of O(log n) given by Chandra, Karloff, and Tovey in [SIAM J. Com-put., 28 (1999), pp. 1998--2029] and provides for the first time a nontrivial lower bound for the case k >= 3. Our results not only hold for the Euclidean norm but extend to arbitrary p-norms with 1 <= p < infinity .