A note on the complexity of the asymmetric traveling salesman problem

DOI10.1016/S0167-6377(96)00037-5zbMath0892.90177MaRDI QIDQ1374382

Weixiong Zhang

Publication date: 4 December 1997

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

branch-and-boundaverage-case complexitysubtour eliminationasymmetric traveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (3)

Combinação de abordagens GLSP e ATSP para o problema de dimensionamento e sequenciamento de lotes de produção de suplementos para nutrição animal ⋮ Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching ⋮ A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem

Cites Work

• Random Trees and the Analysis of Branch and Bound Procedures
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
• Branch-and-Bound Methods: A Survey
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on the complexity of the asymmetric traveling salesman problem