Four-point conditions for the TSP: the complete complexity classification
From MaRDI portal
Publication:2339841
DOI10.1016/j.disopt.2014.09.003zbMath1308.90145OpenAlexW1985142991MaRDI QIDQ2339841
Bettina Klinz, Alexander Tiskin, Gerhard J. Woeginger, Vladimir G. Deǐneko
Publication date: 9 April 2015
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2014.09.003
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items (4)
On the Skeleton of the Polytope of Pyramidal Tours ⋮ Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem ⋮ The multi-stripe travelling salesman problem ⋮ Polynomially solvable cases of the bipartite traveling salesman problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The three-dimensional matching problem in kalmanson matrices
- On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices
- A survey of very large-scale neighborhood search techniques
- Cooperative assignment games with the inverse Monge property
- Extreme Hamiltonian lines
- On-line sorting of twisted sequences in linear time
- A solvable case of the quadratic assignment problem
- The Steiner tree problem in Kalmanson matrices and in circulant matrices
- The quadratic assignment problem. Theory and algorithms
- A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
- The traveling salesman problem and its variations
- Another well-solvable case of the QAP: maximizing the job completion time variance
- Extended neighborhood: Definition and characterization
- The maximum traveling salesman problem on van der Veen matrices
- Perspectives of Monge properties in optimization
- On the recognition of permuted Supnick and incomplete Monge matrices
- The maximum travelling salesman problem on symmetric Demidenko matrices
- Monge properties, discrete convexity and applications
- Sparse Monge matrices arising from scheduling problems
- On the symmetric traveling salesman problem
- Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with monge costs
- Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
- An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
- Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem
- New exponential neighbourhood for polynomially solvable TSPs
- Four point conditions and exponential neighborhoods for symmetric TSP
- One-Sided Monge TSP Is NP-Hard
- Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
- A New Class of Pyramidally Solvable Symmetric Traveling Salesman Problems
- Sometimes Travelling is Easy: The Master Tour Problem
- Hamilton Paths in Grid Graphs
- Edgeconvex Circuits and the Traveling Salesman Problem
- Balancing profits and costs on trees
- Extreme Hamiltonian Circuits. Resolution of the Convex-Odd Case
- Extreme Hamiltonian Circuits. Resolution of the Convex-Even Case
- A solvable case of the traveling salesman problem
This page was built for publication: Four-point conditions for the TSP: the complete complexity classification
