| Article ID: | iaor19981484 |
| Country: | Netherlands |
| Volume: | 20 |
| Issue: | 1 |
| Start Page Number: | 31 |
| End Page Number: | 38 |
| Publication Date: | Jan 1997 |
| Journal: | Operations Research Letters |
| Authors: | Zhang Weixiong |
| Keywords: | programming: branch and bound |
One of the most efficient approaches known for finding an optimal tour of the asymmetric traveling salesman problem (ATSP) is branch-and-bound (BnB) subtour elimination. For two decades, expert opinion has been divided over whether the expected complexity of the ATSP under BnB subtour elimination is polynomial or exponential in the number of cities. We show that the argument for polynomial expected complexity does not hold.