<p>From a quick Google search, it looks like your problem is sometimes called (metric) "facility dispersion." This <a href="http://www.cs.utoronto.ca/~eidan/papers/huristics.pdf" rel="nofollow noreferrer">paper</a> by Ravi, Rosenkrantz, and Tayi seems to prove that your heuristic is a <span class="math-container">$2$</span>-approximation, and that this factor is actually optimal by a reduction to clique.</p>

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

CC BY-SA 4.0
2020-04-13T05:43:35.300Z
2020-04-13T05:43:35.300Z
Jason Gaitonde
<p>I have a metric space <span class="math-container">$(X,d)$</span> and I'd like to find a subset of size k of far away elements. </p>

<p>We can cast this as the following optimization problem <span class="math-container">$\max_{S \subseteq X, |S| = k} ( \min_{i \not = j, i,j \in S} d(i,j))$</span> </p>

<p>For the case <span class="math-container">$k = 2$</span>, 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 <span class="math-container">$m$</span>th stage, picks the point that maximizes the min distance to each of the <span class="math-container">$m-1$</span> previously chosen points. This uses <span class="math-container">$O(k^2|X|)$</span> time.</p>

<p><em>Questions:</em> </p>

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

<p>Similar objective functions, such as <span class="math-container">$\prod_{i \not = j, i,j \in S} d(i,j) $</span>, are also interesting.</p>

<reference-request><approximation-algorithms><optimization><metric-spaces><diameter>
Finding the size $k$ subset in a metric space that maximizes the min distance between elements
Elle Najt
# Finding the size $k$ subset in a metric space that maximizes the min distance between elements

(Asked by: username_0 on 2020-04-12)

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.

**Tags:** reference-request, approximation-algorithms, optimization, metric-spaces, diameter

---

## 1 answers

### Answer by username_1 on 2020-04-13. Score: 3 | Accepted answer

From a quick Google search, it looks like your problem is sometimes called (metric) "facility dispersion." This [paper](http://www.cs.utoronto.ca/~eidan/papers/huristics.pdf) 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.


---

