Local search and the traveling salesman problem: A feature-based characterization of problem hardness

Mersmann Olaf, Bischl Bernd, Bossek Jakob, Trautmann Heike, Wagner Markus, Neumann Frank


Abstract
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. © 2012 Springer-Verlag.



Publication type
Article in Journal

Peer reviewed
Yes

Publication status
Published

Year
2012

Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume
7219 LNCS

Start page
129

Pages range
115-129

Language
English

ISSN
03029743

DOI

Affiliation
Universitat Dortmund,University of Adelaide