Next: MINIMUM DIAMETERS DECOMPOSITION Up: Miscellaneous Previous: MINIMUM K-SUPPLIER Index

### MINIMUM K-MEDIAN

- INSTANCE: Complete graph and distances .

- SOLUTION: A k-median set, i.e., a subset with |V'|=k.

- MEASURE: The sum of the distances from each vertex to its nearest median, i.e.,

- Bad News: Not in APX [341].

- Comment: Reduction from MINIMUM SET COVER. The problem is in APX if a small violation of the cardinality of the median set is allowed.

- Garey and Johnson: ND51