[{"author":[{"full_name":"Mersmann, Olaf","last_name":"Mersmann","first_name":"Olaf"},{"first_name":"Bernd","last_name":"Bischl","full_name":"Bischl, Bernd"},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"},{"first_name":"Markus","full_name":"Wagner, Markus","last_name":"Wagner"},{"first_name":"Jakob","id":"102979","full_name":"Bossek, Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"last_name":"Neumann","full_name":"Neumann, Frank","first_name":"Frank"}],"date_created":"2023-11-14T15:58:59Z","volume":69,"date_updated":"2023-12-13T10:50:41Z","doi":"10.1007/s10472-013-9341-2","title":"A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem","issue":"2","publication_identifier":{"issn":["1012-2443"]},"citation":{"mla":"Mersmann, Olaf, et al. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem.” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 69, no. 2, 2013, pp. 151–182, doi:<a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>.","short":"O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, F. Neumann, Annals of Mathematics and Artificial Intelligence 69 (2013) 151–182.","bibtex":"@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={<a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>}, 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} }","apa":"Mersmann, O., Bischl, B., Trautmann, H., Wagner, M., Bossek, J., &#38; Neumann, F. (2013). A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem. <i>Annals of Mathematics and Artificial Intelligence</i>, <i>69</i>(2), 151–182. <a href=\"https://doi.org/10.1007/s10472-013-9341-2\">https://doi.org/10.1007/s10472-013-9341-2</a>","chicago":"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.” <i>Annals of Mathematics and Artificial Intelligence</i> 69, no. 2 (2013): 151–182. <a href=\"https://doi.org/10.1007/s10472-013-9341-2\">https://doi.org/10.1007/s10472-013-9341-2</a>.","ieee":"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,” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 69, no. 2, pp. 151–182, 2013, doi: <a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>.","ama":"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. <i>Annals of Mathematics and Artificial Intelligence</i>. 2013;69(2):151–182. doi:<a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>"},"intvolume":"        69","page":"151–182","year":"2013","user_id":"102979","department":[{"_id":"819"}],"_id":"48889","language":[{"iso":"eng"}],"keyword":["2-opt","90B06","Classification","Feature selection","MARS","TSP"],"type":"journal_article","publication":"Annals of Mathematics and Artificial Intelligence","status":"public","abstract":[{"lang":"eng","text":"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."}]},{"publication_identifier":{"isbn":["978-3-642-34412-1"]},"page":"115–129","citation":{"chicago":"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 <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>, 115–129. LION 6. Berlin, Heidelberg: Springer-Verlag, 2012.","ieee":"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 <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>, 2012, pp. 115–129.","ama":"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: <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>. LION 6. Springer-Verlag; 2012:115–129.","apa":"Mersmann, O., Bischl, B., Bossek, J., Trautmann, H., Wagner, M., &#38; Neumann, F. (2012). Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness. <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>, 115–129.","bibtex":"@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} }","mla":"Mersmann, Olaf, et al. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>, Springer-Verlag, 2012, pp. 115–129.","short":"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."},"place":"Berlin, Heidelberg","year":"2012","date_created":"2023-11-14T15:58:59Z","author":[{"last_name":"Mersmann","full_name":"Mersmann, Olaf","first_name":"Olaf"},{"full_name":"Bischl, Bernd","last_name":"Bischl","first_name":"Bernd"},{"first_name":"Jakob","id":"102979","full_name":"Bossek, Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"},{"first_name":"Markus","last_name":"Wagner","full_name":"Wagner, Markus"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"date_updated":"2023-12-13T10:48:58Z","publisher":"Springer-Verlag","title":"Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness","publication":"Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219","type":"conference","status":"public","abstract":[{"text":"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.","lang":"eng"}],"department":[{"_id":"819"}],"series_title":"LION 6","user_id":"102979","_id":"48890","extern":"1","language":[{"iso":"eng"}],"keyword":["2-opt","Classification","Feature Selection","MARS","TSP"]}]