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 .
- MEASURE:
The sum of the distances from each vertex to its nearest median, i.e.,
- Bad News:
Not in APX [360].
- Comment:
Reduction from MINIMUM SET COVER.
The problem is in APX if a small violation of the
cardinality of the median set is allowed [360].
Variation in which the vertices lie in a Euclidean space and the
solution consists of points in the space admits a PTAS [40].
- Garey and Johnson: ND51
Viggo Kann
2000-03-20