On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices

DOI10.1007/s10732-010-9127-1zbMath1205.90243OpenAlexW2076697001MaRDI QIDQ623315

George Steiner, Dvir Shabtay, Vladimir G. Deǐneko

Publication date: 14 February 2011

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-010-9127-1

zbMATH Keywords

traveling salesman problemasymptotically optimalstrongly NP-hardsubtour-patching heuristic

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two-machine stochastic flow shops with blocking and the traveling salesman problem
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Permutational extreme values of autocorrelation coefficients and a Pitman test against serial dependence
• Scheduling of parts and robot activities in a two machine robotic cell
• Perspectives of Monge properties in optimization
• Robotic-cell scheduling: special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices
• The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristic
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• A Travelling Salesman Model for the Sequencing of Duties in Bus Crew Rotas
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• On the Flow-Shop Sequencing Problem with No Wait in Process^†

This page was built for publication: On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices