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:
- This seems like a natural enough problem that it's been studied -- what are the keywords to this problem?
- Does this greedy extension work well? What are some other heuristics to try?
- 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.