Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/83888
Citations | ||
Scopus | Web of ScienceĀ® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | A feature-based comparison of local search and the Christofides algorithm for the travelling salesperson problem |
Author: | Nallaperuma, S. Wagner, M. Neumann, F. Bischi, B. Mersmann, O. Trautmann, H. |
Citation: | Proceedings of the 12th Workshop on Foundations of Genetic Algorithms, FOGA XII, 2013 / pp.147-160 |
Publisher: | ACM |
Publisher Place: | online |
Issue Date: | 2013 |
ISBN: | 9781450319904 |
Conference Name: | Workshop on Foundations of Genetic Algorithms (12th : 2013 : Adelaide) |
Editor: | Neumann, F. Jong, K.A.D. |
Statement of Responsibility: | Samadhi Nallaperuma, Markus Wagner, Frank Neumann, Bernd Bischl, Olaf Mersmann, Heike Trautmann |
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: | Traveling Salesperson Problem Approximation Algorithms Local Search Classification Prediction Feature Selection |
DOI: | 10.1145/2460239.2460253 |
Description (link): | http://www.sigevo.org/foga-2013/ |
Published version: | http://dx.doi.org/10.1145/2460239.2460253 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_83888.pdf | Restricted Access | 1.97 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.