The parameterized complexity of local search for TSP, more refined
From MaRDI portal
Publication:378245
DOI10.1007/s00453-012-9685-8zbMath1292.68086MaRDI QIDQ378245
Ondřej Suchý, Jiong Guo, Rolf Niedermeier, Sepp Hartung
Publication date: 11 November 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9685-8
heuristics; NP-hard problem; fixed-parameter tractability; lower bounds based on ETH; problem kernel; W[1-hardness]
68R10: Graph theory (including graph drawing) in computer science
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
05C38: Paths and cycles
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), Parameterized Dynamic Cluster Editing, Improving TSP Tours Using Dynamic Programming over Tree Decompositions., On the parameterized complexity of consensus clustering, Parameterized dynamic cluster editing, Searching for better fill-in, Can local optimality be used for efficient data reduction?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local search: is brute-force avoidable?
- Stable assignment with couples: parameterized complexity and local search
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Searching the \(k\)-change neighborhood for TSP is W[1-hard]
- On the parameterized complexity of multiple-interval graph problems
- On problems without polynomial kernels
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- A partial k-arboretum of graphs with bounded treewidth
- New classes of efficiently solvable generalized traveling salesman problems
- A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
- Which problems have strongly exponential complexity?
- The traveling salesman problem and its variations
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Worst-case analysis of a new heuristic for the travelling salesman problem
- Parametrized complexity theory.
- Tight lower bounds for certain parameterized NP-hard problems
- Kernelization – Preprocessing with a Guarantee
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- On the hardness of losing weight
- A Dynamic Programming Approach to Sequencing Problems
- Incremental List Coloring of Graphs, Parameterized by Conservation
- Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
- Kernelization: New Upper and Lower Bound Techniques
- The Planar Hamiltonian Circuit Problem is NP-Complete
