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: Y. Hamadi, M. Schoenauer (Eds.), Learning and Intelligent Optimization, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 115–129.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
Mersmann, Olaf; Bischl, Bernd; Bossek, Jakob; Trautmann, HeikeLibreCat ; Wagner, Markus; Neumann, Frank
Editor
Hamadi, Youssef; Schoenauer, Marc
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.
Publishing Year
Proceedings Title
Learning and Intelligent Optimization
Page
115–129
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: Hamadi Y, Schoenauer M, eds. Learning and Intelligent Optimization. Springer Berlin Heidelberg; 2012:115–129. doi:https://doi.org/10.1007/978-3-642-34413-8_9
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. In Y. Hamadi & M. Schoenauer (Eds.), Learning and Intelligent Optimization (pp. 115–129). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-34413-8_9
@inproceedings{Mersmann_Bischl_Bossek_Trautmann_Wagner_Neumann_2012, place={Berlin, Heidelberg}, title={Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness}, DOI={https://doi.org/10.1007/978-3-642-34413-8_9}, booktitle={Learning and Intelligent Optimization}, publisher={Springer Berlin Heidelberg}, author={Mersmann, Olaf and Bischl, Bernd and Bossek, Jakob and Trautmann, Heike and Wagner, Markus and Neumann, Frank}, editor={Hamadi, Youssef and Schoenauer, Marc}, year={2012}, pages={115–129} }
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 Learning and Intelligent Optimization, edited by Youssef Hamadi and Marc Schoenauer, 115–129. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. https://doi.org/10.1007/978-3-642-34413-8_9.
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 Learning and Intelligent Optimization, 2012, pp. 115–129, doi: https://doi.org/10.1007/978-3-642-34413-8_9.
Mersmann, Olaf, et al. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” Learning and Intelligent Optimization, edited by Youssef Hamadi and Marc Schoenauer, Springer Berlin Heidelberg, 2012, pp. 115–129, doi:https://doi.org/10.1007/978-3-642-34413-8_9.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search