Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness
O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, F. Neumann, in: Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219, Springer-Verlag, Berlin, Heidelberg, 2012, pp. 115–129.
Download
No fulltext has been uploaded.
Conference Paper
| English
Author
Mersmann, Olaf;
Bischl, Bernd;
Bossek, JakobLibreCat 
;
Trautmann, Heike;
Wagner, Markus;
Neumann, Frank
;
Trautmann, Heike;
Wagner, Markus;
Neumann, FrankDepartment
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.
Keywords
Publishing Year
Proceedings Title
Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219
forms.conference.field.series_title_volume.label
LION 6
Page
115–129
ISBN
LibreCat-ID
Cite this
Mersmann O, Bischl B, Bossek J, Trautmann H, Wagner M, Neumann F. Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness. In: Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219. LION 6. Springer-Verlag; 2012:115–129.
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. Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219, 115–129.
@inproceedings{Mersmann_Bischl_Bossek_Trautmann_Wagner_Neumann_2012, place={Berlin, Heidelberg}, series={LION 6}, title={Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness}, booktitle={Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219}, publisher={Springer-Verlag}, author={Mersmann, Olaf and Bischl, Bernd and Bossek, Jakob and Trautmann, Heike and Wagner, Markus and Neumann, Frank}, year={2012}, pages={115–129}, collection={LION 6} }
Mersmann, Olaf, Bernd Bischl, Jakob Bossek, Heike Trautmann, Markus Wagner, and Frank Neumann. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” In Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219, 115–129. LION 6. Berlin, Heidelberg: Springer-Verlag, 2012.
O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, and F. Neumann, “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness,” in Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219, 2012, pp. 115–129.
Mersmann, Olaf, et al. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219, Springer-Verlag, 2012, pp. 115–129.
Google Scholar
ISBN Search