TY - JOUR
T1 - A note on the complexity of the asymmetric traveling salesman problem
AU - Zhang, Weixiong
N1 - Funding Information:
The authorw ould like to thank Liz Borowsky, Richard Karp, and Richard Korf for helpful dis-cussionsr elatedt o this work, and commentosn an earlyd raft.D uringt hisr esearchth, ea uthorw assup-portedin part by a GTE fellowshipU, CLA Chancel-lot's DissertationY ear Fellowship,N SF Grant No. IRI-9119825a, grant from RockwellI nterna-tional,a ndDARPA Grant, #MDA972-94-2-0010.
PY - 1997/1
Y1 - 1997/1
N2 - 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.
AB - 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.
KW - Average-case complexity
KW - Branch-and-bound
KW - Combinatorial optimization
KW - Traveling salesman problem
UR - https://www.scopus.com/pages/publications/0013165203
U2 - 10.1016/s0167-6377(96)00037-5
DO - 10.1016/s0167-6377(96)00037-5
M3 - Article
AN - SCOPUS:0013165203
SN - 0167-6377
VL - 20
SP - 31
EP - 38
JO - Operations Research Letters
JF - Operations Research Letters
IS - 1
ER -