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

reportActive / Technical Report | Accession Number: ADA315251 | Open PDF

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.

Author(s):
Zhang, Weixiong
Author Organization(s):
UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION SCIENCES INST
Descriptive Note:
Research rept.,
Pagination:
0018

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release, Document Partially Illegible
Distribution Statement:
Availability: Document Partially Illegible.

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
ISI/RS-96-445
Contract/Grant Number(s):
MDA972-94-2-0010
Monitor Series:
DARPA
 Subject Terms
Joint Capability Areas:
JCA_5_Command and Control; JCA_5.3_Planning; JCA_1.2.5_Lessons Learned; JCA_1.2.7_Experimentation; JCA_1.3.2_Personnel Management
Communities of Interest:
Materials and Manufacturing Processes
Descriptor(s):
*MATHEMATICAL MODELS, *OPTIMIZATION, ALGORITHMS, POLYNOMIALS, HEURISTIC METHODS, SYSTEMS ANALYSIS, PERMUTATIONS
Field(s)/Group(s):
Operations Research
Keyword(s):
TRAVELING SAELSMAN PROBLEM
Report Date:
1996 May 01
Creation Date:
1996 Oct 23