Accession Number:

ADA315251

Title:

A Note on the Complexity of the Asymmetric Traveling Salesman Problem.

Descriptive Note:

Research rept.,

Corporate Author:

UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION SCIENCES INST

Personal Author(s):

Report Date:

1996-05-01

Pagination or Media Count:

18.0

Abstract:

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE