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?

Improve this question
$\endgroup$
8
  • $\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, 2015 at 17:18
  • $\begingroup$ I am sorry, you are right. $\endgroup$
    – Barbus
    Jul 1, 2015 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, 2015 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, 2015 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, 2015 at 17:31

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.