Next: MAXIMUM K-FACILITY DISPERSION Up: Miscellaneous Previous: MINIMUM K-MEDIAN Index

### MINIMUM DIAMETERS DECOMPOSITION

- 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].