ND33 M INIMUM M ETRIC B OTTLENECK W ANDERING S ALESPERSON P ROBLEM

     
• I NSTANCE : Set C of m cities, an initial city , a final city , distances satisfying the triangle inequality.
• S OLUTION : A simple path from the initial city to the final city f passing through all cities in C , i.e., a permutation such that and .
• M EASURE : The length of the largest distance in the path, i.e.,
  
  

• Good News: Approximable within 2 [ 172 ].
• Bad News: Not approximable within 2 for any [ 172 ].
• 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 [ 102 ]. 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 [ 13 ].  
• Garey and Johnson: ND24