# Find the subset of k element between n that maximize the total distance

Given a set $Q\subset \mathbb{N}^m$ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm.

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

In my specific case, $Q\subset \{ 0, 1 \} ^m$, thus $d(\cdot,\cdot)$ is equal to the Hamming distance.

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

• @D.W. It's not the same question, since here $Q$ lives in some specific metric space. Assuming it's not $\ell_\infty$, not every graph metric can be realized as a set $Q$, so this problem is potentially easier. – Yuval Filmus Jul 1 '15 at 18:09
• I have redited the question. I hope it can help. – Barbus Jul 2 '15 at 8:46

You can formulate your problem as an instance of integer linear programming (ILP). Introduce variables $y_i$, where $y_i$ indicates whether the $i$th point $x_i$ is included in $S_{max}$, and $z_{i,j}$, with the intended meaning that $z_{i,j} = y_i \land y_j$. Constrain each of these to be zero-or-one integer variables. Add the constraints $\sum_i y_i \le k$ and $z_{i,j} \le y_i$ and $z_{i,j} \le y_j$ and $z_{i,j}=z_{j,i}$. Your goal is to maximize the objective function
$$\sum_{i,j} d(x_i,x_j) z_{i,j}.$$
You can optionally add the extra constraints $y_i+y_j-1 \le z_{i,j}$ and/or $z_{i,j}+z_{j,k}-1 \le z_{i,k}$ and/or $\sum z_{i,j} \le k(k-1)$; this will increase the number of constraints, but might help the solver find a solution more quickly. Now give this ILP instance to an off-the-shelf ILP solver, and hope that it can find a solution efficiently.
If you want a fast heuristic to find an approximate solution, you could try using FPF, as described here. You could also try a greedy algorithm: at the $i$th iteration, select the vertex $x_j$ that increases the total distance of all the vertices selected so far by as much as possible. Neither of these is guaranteed to find an optimal solution, and the solution they output probably won't be optimal, but if you're lucky, they might be not-too-much-worse than optimal.