Local search and the traveling salesman problem: A feature-based characterization of problem hardness
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.
Zitieren als
Mersmann, O., Bischl, B., Bossek, J., Trautmann, H., Wagner, M., & Neumann, F. (2012). Local search and the traveling salesman problem: A feature-based characterization of problem hardness. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (LNCS), 7219 LNCS, 129.Details
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