---
_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'
...
---
_id: '48890'
abstract:
- lang: eng
  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.
author:
- first_name: Olaf
  full_name: Mersmann, Olaf
  last_name: Mersmann
- first_name: Bernd
  full_name: Bischl, Bernd
  last_name: Bischl
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Heike
  full_name: Trautmann, Heike
  last_name: Trautmann
- first_name: Markus
  full_name: Wagner, Markus
  last_name: Wagner
- first_name: Frank
  full_name: Neumann, Frank
  last_name: Neumann
citation:
  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} }'
  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.'
  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.'
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:48:58Z
department:
- _id: '819'
extern: '1'
keyword:
- 2-opt
- Classification
- Feature Selection
- MARS
- TSP
language:
- iso: eng
page: 115–129
place: Berlin, Heidelberg
publication: Revised Selected Papers of the 6th International Conference on Learning
  and Intelligent Optimization - Volume 7219
publication_identifier:
  isbn:
  - 978-3-642-34412-1
publisher: Springer-Verlag
series_title: LION 6
status: public
title: 'Local Search and the Traveling Salesman Problem: A Feature-Based Characterization
  of Problem Hardness'
type: conference
user_id: '102979'
year: '2012'
...