Next: MINIMUM METRIC TRAVELING SALESPERSON
Up: Routing Problems
Previous: Routing Problems
  Index
- 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
Viggo Kann
2000-03-20