Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Fixed-parameter evolutionary algorithms for the euclidean traveling salesperson problem
Author: Nallaperuma, S.
Sutton, A.
Neumann, F.
Citation: 2013 IEEE Congress on Evolutionary Computation, Cancun, Mexico, 20-23 June 2013: pp.2037-2044
Publisher: IEEE
Publisher Place: United States
Issue Date: 2013
ISBN: 9781479904525
Conference Name: IEEE Congress on Evolutionary Computation (2013 : Cancun, Mexico)
Statement of
Samadhi Nallaperuma, Andrew M. Sutton, Frank Neumann
Abstract: Recently, Sutton and Neumann [1] have studied evolutionary algorithms for the Euclidean traveling salesman problem by parameterized runtime analyses taking into account the number of inner points k and the number of cities n. They have shown that simple evolutionary algorithms are XP- algorithms for the problem, i. e., they obtain an optimal solution in expected time O(ng(k)) where g(k) is a function only depending on k. We extend these investigations and design two evolutionary algorithms for the Euclidean Traveling Salesperson problem that run in expected time g(k) poly(n) where k is a parameter denoting the number inner points for the given TSP instance, i. e., they are fixed-parameter tractable evolutionary algorithms for the Euclidean TSP parameterized by the number of inner points. While our first approach is mainly of theoretical interest, our second approach leverages problem structure by directly searching for good orderings of the inner points and provides a novel and highly effective way of tackling this important problem. Our experimental results show that searching for a permutation on the inner points is a significantly powerful practical strategy.
Rights: © 2013 IEEE
DOI: 10.1109/CEC.2013.6557809
Description (link):
Published version:
Appears in Collections:Aurora harvest 4
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access796.77 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.