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


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



Publikationstyp
Forschungsartikel (Zeitschrift)

Begutachtet
Ja

Publikationsstatus
Veröffentlicht

Jahr
2012

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

Band
7219 LNCS

Erste Seite
129

Sprache
Englisch

ISSN
03029743

DOI