2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus Jul 1 '15 at 18:09
  • $\begingroup$ I have redited the question. I hope it can help. $\endgroup$ – Barbus Jul 2 '15 at 8:46
0
$\begingroup$

This problem smells like it might be NP-hard, though I have no proof. If you are looking for a proof of NP-hardness, my advice would be to go through Garey & Johnson (or some other list of NP-complete problems) and look for all problems that seem plausibly related: e.g., ones that involve the hypercube, bitvectors and the Hamming distance, clustering in general metric spaces, or total/average distance in some general metric space. Then, edit your question to list all of those known-NP-complete and plausibly-related problems in your question... and try to see if you can find a reduction from any of them to your problem.

If you are less concerned about theoretical results and instead are looking to solve this in practice as efficiently as possible, some of the techniques in Maximize distance between k nodes in a graph can be adapted to your problem. In particular, I'll suggest two candidate approaches: if you want an exact solution, try using ILP; if you want an approximate solution, try FPF.

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.