Algorithm for selecting a subset of most distant elements

user_461202 0
Viewed 143

Let there be a set of some objects S. Let there be a distance function defined for each pair of objects in S which has the properties of a metric, i.e. d(x, x) = 0, d(x, y) = d(y, x) and d(x, z) <= d(x, y) + d(y, z).

Goal: find a set S' which is a subset of S with given size such that the elements in S' are the farthest apart from each other among all possible S'.

Problem 1: how to define "the farthest apart from each other"? Note that there is only the distance function, the elements themselves don't have any coordinates or such (they may be e.g. strings and the distance be the Levenshtein distance). An obvious candidate is the sum of pairwise distances but I was wondering if there are other (better?) ways, especially with respect to problem 2.

Problem 2: how to actually select of the elements to form S'? An obvious way is to brute-force it, i.e. try all combinations and pick the one with the elements farthest apart but this sounds computationally ineffective. Is there a better way, possibly utilizing some clever definition of elements being "farthest apart".

distance set algorithm
1 Answers

Let's assume that there are N elements in the set S and define the measure of being apart for an element i in S as the distance to the its closest neighbor i. e. l(i) = min(d(i, j)) where 0 <= i, j <= N - 1, i != j.

So the resulting subset S' will contain M elements with the largest values of of l(i) where M is the given size of subset S'

This requires N * (N-1) / 2 calls to distance function d.

Tis algorithm can be somewhat optimized. We can abort calculation of l(i) when we see distance d(i, k) < Cmin where Cmin is the smallest l in already calculated candidates for subset S'. We will have to keep and update the list candidates containing pairs (j, l(j))

P. S. This problem is equivalent to one described in E. Dijkstra "The problem of the most isolated villages

user_23976840
Related