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

DOI10.1007/S10732-010-9127-1MaRDI QIDQ623315zbMATH OpenOpenAlexFDO

Authors Dvir Shabtay, George Steiner, Vladimir G. Deineko

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

asymptotically optimalstrongly NP-hardsubtour-patching heuristictraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• The travelling salesman problem on permuted Monge matrices
• Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• Asymptotic expected performance of some TSP heuristics: An empirical evaluation
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cites work

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

Cited in

(1)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q623315)