Next: MINIMUM METRIC TRAVELING SALESPERSON Up: Routing Problems Previous: Routing Problems Index

### MINIMUM TRAVELING SALESPERSON

- 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 [367].

- Comment: The corresponding maximization problem (finding the tour of maximum length) is approximable within 4/3 if the distance function is symmetric [411] (within by a randomized algorithm [223]) and 63/38 if it is asymmetric [321].

- Garey and Johnson: ND22