---
_id: '46388'
abstract:
- lang: eng
  text: Understanding the behaviour of well-known algorithms for classical NP-hard
    optimisation problems is still a difficult task. With this paper, we contribute
    to this research direction and carry out a feature based comparison of local search
    and the well-known Christofides approximation algorithm for the Traveling Salesperson
    Problem. We use an evolutionary algorithm approach to construct easy and hard
    instances for the Christofides algorithm, where we measure hardness in terms of
    approximation ratio. Our results point out important features and lead to hard
    and easy instances for this famous algorithm. Furthermore, our cross-comparison
    gives new insights on the complementary benefits of the different approaches.
author:
- first_name: Samadhi
  full_name: Nallaperuma, Samadhi
  last_name: Nallaperuma
- first_name: Markus
  full_name: Wagner, Markus
  last_name: Wagner
- first_name: Frank
  full_name: Neumann, Frank
  last_name: Neumann
- first_name: Bernd
  full_name: Bischl, Bernd
  last_name: Bischl
- first_name: Olaf
  full_name: Mersmann, Olaf
  last_name: Mersmann
- first_name: Heike
  full_name: Trautmann, Heike
  id: '100740'
  last_name: Trautmann
  orcid: 0000-0002-9788-8282
citation:
  ama: 'Nallaperuma S, Wagner M, Neumann F, Bischl B, Mersmann O, Trautmann H. A Feature-Based
    Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson
    Problem. In: <i>Proceedings of the Twelfth Workshop on Foundations of Genetic
    Algorithms XII</i>. FOGA XII ’13. Association for Computing Machinery; 2013:147–160.
    doi:<a href="https://doi.org/10.1145/2460239.2460253">10.1145/2460239.2460253</a>'
  apa: Nallaperuma, S., Wagner, M., Neumann, F., Bischl, B., Mersmann, O., &#38; Trautmann,
    H. (2013). A Feature-Based Comparison of Local Search and the Christofides Algorithm
    for the Travelling Salesperson Problem. <i>Proceedings of the Twelfth Workshop
    on Foundations of Genetic Algorithms XII</i>, 147–160. <a href="https://doi.org/10.1145/2460239.2460253">https://doi.org/10.1145/2460239.2460253</a>
  bibtex: '@inproceedings{Nallaperuma_Wagner_Neumann_Bischl_Mersmann_Trautmann_2013,
    place={New York, NY, USA}, series={FOGA XII ’13}, title={A Feature-Based Comparison
    of Local Search and the Christofides Algorithm for the Travelling Salesperson
    Problem}, DOI={<a href="https://doi.org/10.1145/2460239.2460253">10.1145/2460239.2460253</a>},
    booktitle={Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms
    XII}, publisher={Association for Computing Machinery}, author={Nallaperuma, Samadhi
    and Wagner, Markus and Neumann, Frank and Bischl, Bernd and Mersmann, Olaf and
    Trautmann, Heike}, year={2013}, pages={147–160}, collection={FOGA XII ’13} }'
  chicago: 'Nallaperuma, Samadhi, Markus Wagner, Frank Neumann, Bernd Bischl, Olaf
    Mersmann, and Heike Trautmann. “A Feature-Based Comparison of Local Search and
    the Christofides Algorithm for the Travelling Salesperson Problem.” In <i>Proceedings
    of the Twelfth Workshop on Foundations of Genetic Algorithms XII</i>, 147–160.
    FOGA XII ’13. New York, NY, USA: Association for Computing Machinery, 2013. <a
    href="https://doi.org/10.1145/2460239.2460253">https://doi.org/10.1145/2460239.2460253</a>.'
  ieee: 'S. Nallaperuma, M. Wagner, F. Neumann, B. Bischl, O. Mersmann, and H. Trautmann,
    “A Feature-Based Comparison of Local Search and the Christofides Algorithm for
    the Travelling Salesperson Problem,” in <i>Proceedings of the Twelfth Workshop
    on Foundations of Genetic Algorithms XII</i>, 2013, pp. 147–160, doi: <a href="https://doi.org/10.1145/2460239.2460253">10.1145/2460239.2460253</a>.'
  mla: Nallaperuma, Samadhi, et al. “A Feature-Based Comparison of Local Search and
    the Christofides Algorithm for the Travelling Salesperson Problem.” <i>Proceedings
    of the Twelfth Workshop on Foundations of Genetic Algorithms XII</i>, Association
    for Computing Machinery, 2013, pp. 147–160, doi:<a href="https://doi.org/10.1145/2460239.2460253">10.1145/2460239.2460253</a>.
  short: 'S. Nallaperuma, M. Wagner, F. Neumann, B. Bischl, O. Mersmann, H. Trautmann,
    in: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII,
    Association for Computing Machinery, New York, NY, USA, 2013, pp. 147–160.'
date_created: 2023-08-04T15:42:03Z
date_updated: 2023-10-16T13:45:53Z
department:
- _id: '34'
- _id: '819'
doi: 10.1145/2460239.2460253
keyword:
- approximation algorithms
- local search
- traveling salesperson problem
- feature selection
- prediction
- classification
language:
- iso: eng
page: 147–160
place: New York, NY, USA
publication: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms
  XII
publication_identifier:
  isbn:
  - '9781450319904'
publisher: Association for Computing Machinery
series_title: FOGA XII ’13
status: public
title: A Feature-Based Comparison of Local Search and the Christofides Algorithm for
  the Travelling Salesperson Problem
type: conference
user_id: '15504'
year: '2013'
...