In this paper we investigate instances with high integrality ratio of the subtour LP. We determine the instances maximizing the integrality ratio for Rectilinear TSP with up to 10 vertices and for Multidimensional Rectilinear TSP with up to 12 vertices. Based on these instances we give families of instances whose integrality ratio converges to 4 3 for Rectilinear , Multidimensional Rectilinear and Euclidean TSP that have similar structures. We also investigate the concept of local optimality with respect to integrality ratio and develop several algorithms to find instances with high integrality ratio. Furthermore, we describe a family of instances that are hard to solve in practice. The currently fastest TSP solver Concorde needs more than two days to solve an instance from the family with 52 vertices.

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].

The k-Opt and Lin-Kernighan algorithm are two of the most important local search approaches for the Metric TSP. Both start with an arbitrary tour and make local improvements in each step to get a shorter tour. We show that for any fixed k ≥ 3 the approximation ratio of the k-Opt algorithm for Metric TSP is O(√[k]{n}). Assuming the Erdős girth conjecture, we prove a matching lower bound of Ω(√[k]{n}). Unconditionally, we obtain matching bounds for k = 3,4,6 and a lower bound of Ω(n^{2/(3k-3)}). Our most general bounds depend on the values of a function from extremal graph theory and are tight up to a factor logarithmic in the number of vertices unconditionally. Moreover, all the upper bounds also apply to a parameterized version of the Lin-Kernighan algorithm with appropriate parameter. We also show that the approximation ratio of k-Opt for Graph TSP is Ω(log(n)/(log log(n))) and O({log(n)/(log log(n))}^{log₂(9)+ε}) for all ε > 0.