Article ID: | iaor20133659 |
Volume: | 67 |
Issue: | 1 |
Start Page Number: | 89 |
End Page Number: | 110 |
Publication Date: | Sep 2013 |
Journal: | Algorithmica |
Authors: | Niedermeier Rolf, Guo Jiong, Hartung Sepp, Such Ondrej |
Keywords: | combinatorial optimization, search, heuristics: local search |
We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (defining the local search area) ‘Edge Exchange’ and ‘Max‐Shift’. We perform studies with respect to the distance measures ‘Swap’ and ‘