Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/78478
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Local search and the traveling salesman problem: A feature-based characterization of problem hardness |
Author: | Mersmann, O. Bischl, B. Bossek, J. Trautmann, H. Wagner, M. Neumann, F. |
Citation: | Learning and Intelligent Optimization: 6th International Conference, LION 6, Paris, France, January 16-20, 2012, Revised Selected Papers / Y. Hamadi and M. Schoenauer (eds.): pp.115–129 |
Publisher: | Springer-Verlag |
Publisher Place: | Germany |
Issue Date: | 2012 |
Series/Report no.: | Lecture Notes in Computer Science |
ISBN: | 9783642344121 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Conference on Learning and Intelligent Optimization (6th : 2012 : Paris, France) |
Editor: | Hamadi, Y. Schoenauer, M. |
Statement of Responsibility: | Olaf Mersmann, Bernd Bischl, Jakob Bossek, Heike Trautmann, Markus Wagner and Frank Neumann |
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. © 2012 Springer-Verlag. |
Keywords: | TSP 2-opt Classification Feature Selection MARS. |
Rights: | Copyright Springer-Verlag Berlin Heidelberg 2012 |
DOI: | 10.1007/978-3-642-34413-8_9 |
Published version: | http://dx.doi.org/10.1007/978-3-642-34413-8_9 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.