I would like to know the name of the following problem. I assume it is NP-hard, but a link to a proof of such would also be appreciated.
Say we have some set of points in a metric space $S = \{p_1,...,p_n\}$. There are some labels $L=\{l_1,...,l_m\}$. Point are labelled by a surjective function $f_l: S \rightarrow L$. Find the subset of points C such that:
- $\{f_l(c): c\in{}C\}=L$ (L is covered)
- $Q=\sum_{c,c'\in{}C}{d(c, c')}$ is minimised (the points are as close as possible)
- Note that this implies $|C| = |L|$, that C is of minimal size
- Also note we can assume $c\neq{}c'$ without loss of generality since $d(p_i, p_i) = 0$