Next: MINIMUM DIAMETERS DECOMPOSITION
Previous: MINIMUM K-SUPPLIER
and distances .
A k-median set, i.e., a subset
The sum of the distances from each vertex to its nearest median, i.e.,
- Bad News:
Not in APX .
Reduction from MINIMUM SET COVER.
The problem is in APX if a small violation of the
cardinality of the median set is allowed .
Variation in which the vertices lie in a Euclidean space and the
solution consists of points in the space admits a PTAS .
- Garey and Johnson: ND51