3
$\begingroup$

Given a set $Q$ of $n$ points, we want to find the subset $S_\max \subset Q$ of $k$ elements that maximize the total distance between them.

$$S_\max = \max_S \sum_{\substack{ i,j\in S\\ i \neq j}} d(x_i,x_j)$$

where in my case $x_i$ is a boolean vector and the distance considered is the Manhattan/Hamming distance.

Is there any efficient way to solve this problem? Is it possible to rewrite it in another simpler way?

$\endgroup$
  • $\begingroup$ The unique solution is to let $k$ be the set of all points. Are you perhaps using "$k$" in two different senses--one to name an arbitrary set and another to establish a constraint on its cardinality? Could you say anything about this "distance"? It might be possible to capitalize on specific properties of distances if, say, these were points in the plane and the distance were Euclidean, whereas the solution for arbitrary metrics might be more difficult. $\endgroup$ – whuber Jul 1 '15 at 17:18
  • $\begingroup$ I am sorry, you are right. $\endgroup$ – Barbus Jul 1 '15 at 17:24
  • $\begingroup$ Given a set $Q$ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them. $S_{max} = \max_S\sum_{\mbox{$\begin{array}{c} i,j\in S\\ i\not=j\end{array}$}}d(xi,xj)$ In my case I use the Manhattan distance since $x_i$ is a boolean vector $\endgroup$ – Barbus Jul 1 '15 at 17:26
  • $\begingroup$ Isn't that a non-decreasing function? The more points you have the larger the maximum? Like @Barbus said, let k=n. $\endgroup$ – dpmcmlxxvi Jul 1 '15 at 17:26
  • $\begingroup$ Those are useful clarifications, Barbus. Please edit your post to include them. Incidentally, I believe the Manhattan distance in this case is usually referred to as the Hamming distance. $\endgroup$ – whuber Jul 1 '15 at 17:31
1
$\begingroup$

This is known as the farthest-point clustering problem. It is NP-hard, but there is a approximation algorithm: https://en.wikipedia.org/wiki/Farthest-first_traversal. The problem has normally been studied with the Euclidean distance metric, but you can apply the same greedy algorithm to the Hamming distance, too, to get an approximate (but not necessarily optimal) solution.

$\endgroup$

Your Answer

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