Local Search and the Traveling Salesman Problem: A Feature-Based
Characterization of Problem Hardness
Olaf Mersmann, Bernd Bischl, Jakob Bossek, Heike Trautmann,
Markus Wagner, and Frank Neumann
With this paper we contribute to the understanding of the success of
2-opt based local search algorithms for solving the traveling
salesman problem (TSP). Although $2$-opt is widely used in practice,
it is hard to understand its success from a theoretical
perspective. We take a statistical approach and examine the features
of TSP instances that make the problem either hard or easy to
solve. As a measure of problem difficulty for 2-opt we use the
approximation ratio that it achieves on a given instance. Our
investigations point out important features that make TSP instances
hard or easy to be approximated by $2$-opt.