@article{48889,
  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.}},
  author       = {{Mersmann, Olaf and Bischl, Bernd and Trautmann, Heike and Wagner, Markus and Bossek, Jakob and Neumann, Frank}},
  issn         = {{1012-2443}},
  journal      = {{Annals of Mathematics and Artificial Intelligence}},
  keywords     = {{2-opt, 90B06, Classification, Feature selection, MARS, TSP}},
  number       = {{2}},
  pages        = {{151–182}},
  title        = {{{A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem}}},
  doi          = {{10.1007/s10472-013-9341-2}},
  volume       = {{69}},
  year         = {{2013}},
}

@inproceedings{48890,
  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.}},
  author       = {{Mersmann, Olaf and Bischl, Bernd and Bossek, Jakob and Trautmann, Heike and Wagner, Markus and Neumann, Frank}},
  booktitle    = {{Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219}},
  isbn         = {{978-3-642-34412-1}},
  keywords     = {{2-opt, Classification, Feature Selection, MARS, TSP}},
  pages        = {{115–129}},
  publisher    = {{Springer-Verlag}},
  title        = {{{Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness}}},
  year         = {{2012}},
}