Next: MINIMUM CHINESE POSTMAN FOR Up: Routing Problems Previous: MINIMUM METRIC TRAVELING K-SALESPERSON Index

### MINIMUM METRIC BOTTLENECK WANDERING SALESPERSON PROBLEM

- 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