Four-point conditions for the TSP: the complete complexity classification

DOI10.1016/j.disopt.2014.09.003zbMath1308.90145MaRDI 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

zbMATH Keywords

traveling salesman problem; four-point condition; polynomially solvable case

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

Related Items

On the Skeleton of the Polytope of Pyramidal Tours, The multi-stripe travelling salesman problem, Polynomially solvable cases of the bipartite traveling salesman problem, Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing 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