4

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?

nicoguaro
  • 8,500
  • 6
  • 23
  • 49
  • 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. – whuber Jul 01 '15 at 17:18
  • I am sorry, you are right. –  Jul 01 '15 at 17:24
  • 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

     –  Jul 01 '15 at 17:26
  • Isn't that a non-decreasing function? The more points you have the larger the maximum? Like @Barbus said, let k=n. – dpmcmlxxvi Jul 01 '15 at 17:26
  • 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. – whuber Jul 01 '15 at 17:31
  • the number of elements $k$ in the subset $S$ is fixed. –  Jul 01 '15 at 17:36
  • Here is an approximate solution to a similar question. – dpmcmlxxvi Jul 01 '15 at 17:46
  • Try to see Edwards blossom algorithm. – ttnphns Jul 01 '15 at 18:30

1 Answers1

1

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.

D.W.
  • 400
  • 3
  • 16