On the stochastic complexity of the asymmetric traveling salesman problem

DOI10.1016/0377-2217(89)90230-0MaRDI QIDQ915656zbMATH OpenOpenAlexFDO

Authors Hans-Ulrich Dost, Johannes Terno, Guntram Scheithauer

Publication date 1989

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(89)90230-0

zbMATH Keywords

discrete optimizationstochastic complexitycombinatorial analysispolynomial boundasymmetric traveling salesman

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A note on the complexity of the asymmetric traveling salesman problem
• scientific article; zbMATH DE number 4149903
• Probabilistic prediction of the complexity of traveling salesman problems based on approximating the complexity distribution from experimental data
• The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
• Exact solution of large-scale, asymmetric traveling salesman problems

Cites work

• scientific article; zbMATH DE number 3908167 (Why is no real title available?)
• scientific article; zbMATH DE number 3918092 (Why is no real title available?)
• scientific article; zbMATH DE number 3763671 (Why is no real title available?)
• scientific article; zbMATH DE number 3566552 (Why is no real title available?)
• scientific article; zbMATH DE number 3583204 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A new extension principle algorithm for the traveling salesman problem
• A restricted Lagrangean approach to the traveling salesman problem
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• On some techniques useful for solution of transportation network problems
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• Probabilistic analysis of solving the assignment problem for the traveling salesman problem
• Random Trees and the Analysis of Branch and Bound Procedures
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem

Cited in

(7)

• A study of complexity transitions on the asymmetric traveling salesman problem
• On Random Symmetric Travelling Salesman Problems
• Technical Note—On Traveling Salesman Games with Asymmetric Costs
• scientific article; zbMATH DE number 4149903 (Why is no real title available?)
• Probabilistic prediction of the complexity of traveling salesman problems based on approximating the complexity distribution from experimental data
• A sharp deviation inequality for the stochastic traveling salesman problem
• Polarity and the complexity of the shooting experiment

This page was built for publication: On the stochastic complexity of the asymmetric traveling salesman problem

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