On the stochastic complexity of the asymmetric traveling salesman problem

DOI10.1016/0377-2217(89)90230-0zbMATH Open0702.90068OpenAlexW1984891736MaRDI QIDQ915656FDOQ915656

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

Recommendations

• A note on the complexity of the asymmetric traveling salesman problem
• Publication:3479820
• 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

zbMATH Keywords

discrete optimizationstochastic complexitycombinatorial analysispolynomial boundasymmetric traveling salesman

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On some techniques useful for solution of transportation network problems
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• Title not available (Why is that?)
• A restricted Lagrangean approach to the traveling salesman problem
• Title not available (Why is that?)
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• Title not available (Why is that?)
• Random Trees and the Analysis of Branch and Bound Procedures
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• Title not available (Why is that?)
• Probabilistic analysis of solving the assignment problem for the traveling salesman problem
• Title not available (Why is that?)
• A new extension principle algorithm for the traveling salesman problem

Cited In (5)

• On Random Symmetric Travelling Salesman Problems
• Technical Note—On Traveling Salesman Games with Asymmetric Costs
• Title not available (Why is that?)
• 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)