Find the set of K elements between n that maximize the total distance

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?

• 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. Jul 1 '15 at 17:18
• I am sorry, you are right.
– Barbus
Jul 1 '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
– Barbus
Jul 1 '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. Jul 1 '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. Jul 1 '15 at 17:31