The parameterized complexity of local search for TSP, more refined

DOI10.1007/s00453-012-9685-8zbMath1292.68086OpenAlexW2113885662MaRDI 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

zbMATH Keywords

heuristicsNP-hard problemfixed-parameter tractabilitylower bounds based on ETHproblem kernelW[1-hardness]

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Methods for determining cycles of a specific length in undirected graphs with edge weights, Can local optimality be used for efficient data reduction?, Parameterized dynamic cluster editing, Searching for better fill-in, On the parameterized complexity of consensus clustering, 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.

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