Searching the \(k\)-change neighborhood for TSP is W[1]-hard
From MaRDI portal
Publication:924881
DOI10.1016/j.orl.2007.02.008zbMath1166.90364OpenAlexW2072008504MaRDI QIDQ924881
Publication date: 29 May 2008
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2007.02.008
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Search theory (90B40) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (15)
The parameterized complexity of local search for TSP, more refined ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Can local optimality be used for efficient data reduction? ⋮ Local search: is brute-force avoidable? ⋮ Local search for string problems: brute-force is essentially optimal ⋮ Parameterized complexity and local search approaches for the stable marriage problem with ties ⋮ Stable assignment with couples: parameterized complexity and local search ⋮ The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ Searching for better fill-in ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ Parameterized approximation of dominating set problems ⋮ On the parameterized complexity of consensus clustering ⋮ Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP ⋮ The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
Cites Work
This page was built for publication: Searching the \(k\)-change neighborhood for TSP is W[1]-hard
