The Parameterized Complexity of Local Search for TSP, More Refined
| Autor: | Jiong Guo, Ondřej Suchý, Rolf Niedermeier, Sepp Hartung |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Exponential time hypothesis General Computer Science business.industry Applied Mathematics Parameterized complexity Travelling salesman problem Distance measures Computer Science Applications Planar graph Combinatorics Reduction (complexity) symbols.namesake Theory of computation symbols Local search (optimization) business Mathematics |
| Zdroj: | Algorithmica. 67:89-110 |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-012-9685-8 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink