- 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 [254].*Bad News:*Not approximable within 2 for any [254].*Comment:*The same positive and negative results hold even if*X*is a set of point in*d*-dimensional space with the or metric. If the metric is used then the upper bound is 1.969 [152]. 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 [26].*Garey and Johnson:*ND24