Finding the size $k$ subset in a metric space that maximizes the min distance between elements

Question

I have a metric space $(X,d)$ and I'd like to find a subset of size k of far away elements.

We can cast this as the following optimization problem $\max_{S \subseteq X, |S| = k} ( \min_{i \not = j, i,j \in S} d(i,j))$

For the case $k = 2$, there is a well known 2-approximation, which picks an arbitrary point and finds the point that is furthest from it. There is a natural extension of this idea, which at the $m$th stage, picks the point that maximizes the min distance to each of the $m-1$ previously chosen points. This uses $O(k^2|X|)$ time.

Questions:

1. This seems like a natural enough problem that it's been studied -- what are the keywords to this problem?
2. Does this greedy extension work well? What are some other heuristics to try?
3. For fixed $k$, is there a constant factor approximation with query size $O(|X|)$? Can one obtain a decent approximation in better than $O(k^2|X|^k)$ time?

Similar objective functions, such as $\prod_{i \not = j, i,j \in S} d(i,j) $, are also interesting.

Answer 1

From a quick Google search, it looks like your problem is sometimes called (metric) "facility dispersion." This paper by Ravi, Rosenkrantz, and Tayi seems to prove that your heuristic is a $2$-approximation, and that this factor is actually optimal by a reduction to clique.

I skimmed it, so I might be missing some subtle points, but the idea of the proof seems quite simple: take an optimal $S\subseteq X$ with $\vert S\vert=k$, with objective value $\mathsf{OPT}$. Note that the $k$th point you add in the greedy algorithm will attain the closest distance (to another point) in the greedy solution, so it suffices to show that the last point you add must have distance at least $\mathsf{OPT}/2$ from the previous $k-1$ points you selected. This is seen by noting that the $k$ (open) metric balls of radius $\mathsf{OPT}/2$ around each point in $S$ are disjoint; as a result, at least one of these balls does not contain any of the first $k-1$ points you have chosen. The respective center in $S$ is therefore an option at step $k$ which attains a pairwise distance of at least $\mathsf{OPT}/2$ from all previously chosen points, so the same must be true of the greedy point chosen at the $k$th step.