Next: MAXIMUM K-FACILITY DISPERSION
Up: Miscellaneous
Previous: MINIMUM K-MEDIAN
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A decomposition of the graph into two factors, F1 and F2, with
equal diameters.
- MEASURE:
The diameter of F1.
- Bad News:
Not approximable within 3/2
for any
[385].
- Comment:
Variation in which the diameters of F1 and F2 do not need to be
equal, and where the objective is to minimize the sum of the diameters,
is not approximable within 5/4
[385].
Viggo Kann
1999-04-22