Given some finite set $X$, containing $n$ distinct objects $x_i$, and a distance metric $d:X\times X \rightarrow \mathbb{R}^{+}$, I want an algorithm to (approximately) find the subset of size $m$ such that average distance between elements in the subset is maximized:

$$\max \frac{1}{m}\sum_{i=2}^{m} \sum_{j<i} d(x_i,x_j) $$

Here, $d(x_i,x_j) = 0 \iff i=j$. I am sure this must be a classic problem, but I can't find quite this formulation. It is similar to the assignment and longest path problems, and it is probably NP-hard in general, but I am interested in some methods that could be scalable to tens of thousands of elements, and in particular when evaluation of $d$ is nontrivial (i.e. solution of a pde).

I can imagine doing this in a greedy way, starting at one point and adding one from there, but I can't afford to search the whole set every step...

Edit: My thinking here is that I need some kind of sampling based approach, perhaps drawing random pairs and trying to infer estimate the variability in the set of distances by fitting to distribution. Since this is real data, I don't expect that it will be very unusually clustered - I'd guess there would be a large number that are reasonably similar (small distances) and some clusters of outliers that are similar to each other but distinct from the bulk. That's what the input set looks like, very roughly. If anyone has any references in this respect (or another, totally different way to do it) I'd very grateful.

  • $\begingroup$ Oh just because if $i=1$, there is no $j<i$ (equivalently, for a distance function $d(x_i,x_i) = 0$ $\forall i$) $\endgroup$
    – JP Janet
    Feb 12, 2017 at 4:02
  • 1
    $\begingroup$ Does $d (x_i, x_j) = 0$ imply that $x_i = x_j$? $\endgroup$ Feb 12, 2017 at 23:10
  • $\begingroup$ Yes, I have edited the question to reflect this. Numerically I might have badly conditioned cases where $d(x_i,x_j)$ is small (I haven't calculated all pairwise distances) $\endgroup$
    – JP Janet
    Feb 13, 2017 at 1:45
  • $\begingroup$ You have a weighted graph on set $\mathcal X$ such that the edge $\{x_i, x_j\}$ has weight $d (x_i, x_j) \geq 0$. You want to find the $m$-clique with the maximal sum of edge weights. $\endgroup$ Feb 13, 2017 at 23:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.