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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1996
Accession Number
ADA315251

Entities

People

  • Weixiong Zhang

Organizations

  • University of Southern California

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Classification
  • Computer Science
  • Elimination
  • Exponential Functions
  • Information Science
  • Operations Research
  • Optical Scanning
  • Permutations
  • Polynomials
  • Probability
  • Security
  • Standards
  • Statistical Analysis
  • Trees (Data Structures)

Fields of Study

  • Mathematics

Readers

  • Operations Research