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) : Zhang, Weixiong

PDF Url : ADA315251

Report Date : MAY 1996

Pagination or Media Count : 18

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.

Descriptors :   *MATHEMATICAL MODELS, *OPTIMIZATION, ALGORITHMS, POLYNOMIALS, HEURISTIC METHODS, SYSTEMS ANALYSIS, PERMUTATIONS.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE