Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
From MaRDI portal
Publication:5111717
DOI10.4230/LIPIcs.ESA.2017.30zbMath1442.68286arXiv1703.05559OpenAlexW2604874681MaRDI QIDQ5111717
Marek Cygan, Arkadiusz Socała, Łukasz Kowalik
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1703.05559
Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Finding and counting permutations via CSPs ⋮ Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
Cites Work
- The parameterized complexity of local search for TSP, more refined
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- Searching the \(k\)-change neighborhood for TSP is W[1-hard]
- On two techniques of combining branching and treewidth
- Pathwidth of cubic graphs and exact algorithms
- How easy is local search?
- Dynamic programming meets the principle of inclusion and exclusion
- Treewidth. Computations and approximations
- An effective implementation of the Lin-Kernighan traveling salesman heuristic
- Worst-case analysis of a new heuristic for the travelling salesman problem
- Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
- On exact algorithms for treewidth
- Finding Induced Subgraphs via Minimal Triangulations
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- A Dynamic Programming Approach to Sequencing Problems
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
- On Finding and Verifying Locally Optimal Solutions
- New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
- Fine-grained complexity analysis of two classic TSP variants
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
- A Method for Solving Traveling-Salesman Problems
- Parameterized Algorithms
- Computer Solutions of the Traveling Salesman Problem
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
This page was built for publication: Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
