A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem
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.
Download
No fulltext has been uploaded.
Conference Paper
| English
Author
Nallaperuma, Samadhi;
Wagner, Markus;
Neumann, Frank;
Bischl, Bernd;
Mersmann, Olaf;
Trautmann, HeikeLibreCat 
Abstract
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.
Keywords
Publishing Year
Proceedings Title
Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII
forms.conference.field.series_title_volume.label
FOGA XII ’13
Page
147–160
ISBN
LibreCat-ID
Cite this
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: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII. FOGA XII ’13. Association for Computing Machinery; 2013:147–160. doi:10.1145/2460239.2460253
Nallaperuma, S., Wagner, M., Neumann, F., Bischl, B., Mersmann, O., & Trautmann, H. (2013). A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem. Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, 147–160. https://doi.org/10.1145/2460239.2460253
@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={10.1145/2460239.2460253}, 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} }
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 Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, 147–160. FOGA XII ’13. New York, NY, USA: Association for Computing Machinery, 2013. https://doi.org/10.1145/2460239.2460253.
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 Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, 2013, pp. 147–160, doi: 10.1145/2460239.2460253.
Nallaperuma, Samadhi, et al. “A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem.” Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, Association for Computing Machinery, 2013, pp. 147–160, doi:10.1145/2460239.2460253.
Google Scholar
ISBN Search