- INSTANCE:
Set
*C*of*m*cities, distances for each pair of cities . - SOLUTION:
A tour of
*C*, i.e., a permutation . - MEASURE:
The length of the tour, i.e.,
.

*Bad News:*NPO-complete [388].*Comment:*The corresponding maximization problem (finding the tour of maximum length) is approximable within 4/3 if the distance function is symmetric [434] (within by a randomized algorithm [240]) and 63/38 if it is asymmetric [337].*Garey and Johnson:*ND22