The Parameterized Complexity of Local Search for TSP, More Refined

The Parameterized Complexity of Local Search for TSP, More Refined

0.00 Avg rating0 Votes
Article ID: iaor20133659
Volume: 67
Issue: 1
Start Page Number: 89
End Page Number: 110
Publication Date: Sep 2013
Journal: Algorithmica
Authors: , , ,
Keywords: combinatorial optimization, search, heuristics: local search
Abstract:

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 ‘r‐Swap’, ‘Reversal’ and ‘r‐Reversal’, and ‘Edit’, achieving both fixed‐parameter tractability and W[1]‐hardness results. In particular, from the parameterized reduction showing W[1]‐hardness we infer running time lower bounds (based on the exponential time hypothesis) for all corresponding distance measures. Moreover, we provide non‐existence results for polynomial‐size problem kernels and we show that some in general W[1]‐hard problems turn fixed‐parameter tractable when restricted to planar graphs.

Reviews

Required fields are marked *. Your email address will not be published.