A Note on the Complexity of the Asymmetric Traveling Salesman Problem.
UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION SCIENCES INST
Pagination or Media Count:
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.
- Operations Research