Next: MINIMUM CHINESE POSTMAN FOR
Up: Routing Problems
Previous: MINIMUM METRIC TRAVELING K-SALESPERSON
  Index
- INSTANCE:
Set C of m cities, an initial city
,
a final city
,
distances
satisfying the triangle inequality.
- SOLUTION:
A simple path from the initial city s to the final city f passing through
all cities in C, i.e., a permutation
such that
and
.
- MEASURE:
The length of the largest distance in the path, i.e.,
- Good News:
Approximable within 2 [237].
- Bad News:
Not approximable within 2
for any
[237].
- Comment:
The same positive and negative results hold even if X is a set of point in
d-dimensional space with the L1 or
metric. If the L2 metric
is used then the upper bound is 1.969 [141].
The corresponding maximization problem called MAXIMUM SCATTER TSP, where
the length of the shortest distance in the path is maximized, is approximable
within 2, but not approximable within
for any
[25].
- Garey and Johnson: ND24
Next: MINIMUM CHINESE POSTMAN FOR
Up: Routing Problems
Previous: MINIMUM METRIC TRAVELING K-SALESPERSON
  Index
Viggo Kann
1999-04-22