MINIMUM K-MEDIAN

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

INSTANCE: Complete graph $G=\left(V,E\right)$ and distances $d(e)\in N$ .
SOLUTION: A k-median set, i.e., a subset $V' \subseteq V$ with $\vert V'\vert=k$ .
MEASURE: The sum of the distances from each vertex to its nearest median, i.e.,

$\begin{displaymath} \sum_{v \in V}\min_{w \in V'} d(v,w). \end{displaymath}$
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