MINIMUM K-MEDIAN

• 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.,

  
  

  $$\sum_{v \in V}\min_{w \in V'} d(v,w).$$
  
  

  
  

• 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