- 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