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