A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem

O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, F. Neumann, Annals of Mathematics and Artificial Intelligence 69 (2013) 151–182.

Download
No fulltext has been uploaded.
Journal Article | English
Author
Mersmann, O; Bischl, B; Trautmann, HeikeLibreCat ; Wagner, M; Bossek, JakobLibreCat ; Neumann, F
Abstract
Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesperson 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
Journal Title
Annals of Mathematics and Artificial Intelligence
Volume
69
Page
151–182
LibreCat-ID

Cite this

Mersmann O, Bischl B, Trautmann H, Wagner M, Bossek J, Neumann F. A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem. Annals of Mathematics and Artificial Intelligence. 2013;69:151–182.
Mersmann, O., Bischl, B., Trautmann, H., Wagner, M., Bossek, J., & Neumann, F. (2013). A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem. Annals of Mathematics and Artificial Intelligence, 69, 151–182.
@article{Mersmann_Bischl_Trautmann_Wagner_Bossek_Neumann_2013, title={A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem}, volume={69}, journal={Annals of Mathematics and Artificial Intelligence}, author={Mersmann, O and Bischl, B and Trautmann, Heike and Wagner, M and Bossek, Jakob and Neumann, F}, year={2013}, pages={151–182} }
Mersmann, O, B Bischl, Heike Trautmann, M Wagner, Jakob Bossek, and F Neumann. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem.” Annals of Mathematics and Artificial Intelligence 69 (2013): 151–182.
O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, and F. Neumann, “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem,” Annals of Mathematics and Artificial Intelligence, vol. 69, pp. 151–182, 2013.
Mersmann, O., et al. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem.” Annals of Mathematics and Artificial Intelligence, vol. 69, 2013, pp. 151–182.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar