Abstract. The [Formula: see text]-Opt heuristic is a simple improvement heuristic for the traveling salesman problem. It starts with an arbitrary tour and then repeatedly replaces [Formula: see text] edges of the tour by [Formula: see text] other edges, as long as this yields a shorter tour. We will prove that for the 2-dimensional Euclidean traveling salesman problem with [Formula: see text] cities the approximation ratio of the [Formula: see text]-Opt heuristic is [Formula: see text]. This improves the upper bound of [Formula: see text] given by Chandra, Karloff, and Tovey in [ SIAM J. Comput., 28 (1999), pp. 1998–2029] and provides for the first time a nontrivial lower bound for the case [Formula: see text]. Our results not only hold for the Euclidean norm but extend to arbitrary [Formula: see text]-norms with [Formula: see text].