A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson 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, Olaf;
Bischl, Bernd;
Trautmann, Heike;
Wagner, Markus;
Bossek, JakobLibreCat 
;
Neumann, Frank
;
Neumann, FrankDepartment
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.
Keywords
Publishing Year
Journal Title
Annals of Mathematics and Artificial Intelligence
Volume
69
Issue
2
Page
151–182
ISSN
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 Salesperson Problem. Annals of Mathematics and Artificial Intelligence. 2013;69(2):151–182. doi:10.1007/s10472-013-9341-2
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 Salesperson Problem. Annals of Mathematics and Artificial Intelligence, 69(2), 151–182. https://doi.org/10.1007/s10472-013-9341-2
@article{Mersmann_Bischl_Trautmann_Wagner_Bossek_Neumann_2013, title={A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem}, volume={69}, DOI={10.1007/s10472-013-9341-2}, number={2}, journal={Annals of Mathematics and Artificial Intelligence}, author={Mersmann, Olaf and Bischl, Bernd and Trautmann, Heike and Wagner, Markus and Bossek, Jakob and Neumann, Frank}, year={2013}, pages={151–182} }
Mersmann, Olaf, Bernd Bischl, Heike Trautmann, Markus Wagner, Jakob Bossek, and Frank Neumann. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem.” Annals of Mathematics and Artificial Intelligence 69, no. 2 (2013): 151–182. https://doi.org/10.1007/s10472-013-9341-2.
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 Salesperson Problem,” Annals of Mathematics and Artificial Intelligence, vol. 69, no. 2, pp. 151–182, 2013, doi: 10.1007/s10472-013-9341-2.
Mersmann, Olaf, et al. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem.” Annals of Mathematics and Artificial Intelligence, vol. 69, no. 2, 2013, pp. 151–182, doi:10.1007/s10472-013-9341-2.
Google Scholar