Next: MINIMUM METRIC BOTTLENECK WANDERING
Up: Routing Problems
Previous: MINIMUM GEOMETRIC TRAVELING SALESPERSON
Set C of m cities, an initial city ,
satisfying the triangle inequality.
A collection of k subtours, each containing the initial city s, such that
each city is in at least one subtour.
The maximum length of the k subtours.
- Good News:
Approximable within 1-1/k plus the performance ratio of the MINIMUM METRIC TRAVELING SALESPERSON PROBLEM,
The non-metric variation in which the graph is a tree and k possibly
different initial cities are given in the input is approximable within