Next: MINIMUM DIAMETERS DECOMPOSITION
Up: Miscellaneous
Previous: MINIMUM K-SUPPLIER
  Index
- 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
Viggo Kann
1999-04-22