---
_id: '48889'
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.
author:
- first_name: Olaf
  full_name: Mersmann, Olaf
  last_name: Mersmann
- first_name: Bernd
  full_name: Bischl, Bernd
  last_name: Bischl
- first_name: Heike
  full_name: Trautmann, Heike
  last_name: Trautmann
- first_name: Markus
  full_name: Wagner, Markus
  last_name: Wagner
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Frank
  full_name: Neumann, Frank
  last_name: Neumann
citation:
  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>
  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>
  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} }'
  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>.'
  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.
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:50:41Z
department:
- _id: '819'
doi: 10.1007/s10472-013-9341-2
intvolume: '        69'
issue: '2'
keyword:
- 2-opt
- 90B06
- Classification
- Feature selection
- MARS
- TSP
language:
- iso: eng
page: 151–182
publication: Annals of Mathematics and Artificial Intelligence
publication_identifier:
  issn:
  - 1012-2443
status: public
title: A Novel Feature-Based Approach to Characterize Algorithm Performance for the
  Traveling Salesperson Problem
type: journal_article
user_id: '102979'
volume: 69
year: '2013'
...