On 05.01.2012 at 12:20 in S6, there is the following noon lecture:
The Parameterized Complexity of Local Search for TSP
University of Saarland
We give more refined view on the parameterized complexity of local search for the Travelling Salesperson Problem (TSP), extending previous work. So far, its parameterized complexity has been investigated with respect to the distance measures (which define the local search area) "Edge Exchange" and "Max-Shift". We perform studies with respect to the distance measures "Swap" and "m-Swap", "Reversal" and "m-Reversal", and "Edit", achieving both fixed-parameter tractability and W-hardness results. Moreover, we will mention non-existence results for polynomial-size problem kernels and we will show that some in general W-hard problems turn fixed-parameter tractable when restricted to planar graphs.
This is joint work with Jiong Guo, Sepp Hartung, and Rolf Niedermeier.
Modified: 19. 10. 2010