On the stochastic complexity of the asymmetric traveling salesman problem

DOI10.1016/0377-2217(89)90230-0zbMath0702.90068OpenAlexW1984891736MaRDI QIDQ915656

Hans-Ulrich Dost, Guntram Scheithauer, Johannes Terno

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

combinatorial analysisdiscrete optimizationstochastic complexitypolynomial boundasymmetric traveling salesman

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A restricted Lagrangean approach to the traveling salesman problem
• A new extension principle algorithm for the traveling salesman problem
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• On some techniques useful for solution of transportation network problems