Optimal solution for Weighted points problem

Question

Problem:

Fix a constant $k$. Given a set of $2d$-dimensional points $N = \{N_1, N_2, N_3, \dots, N_n\}$, each associated with an arbitrary weight, find a set of points $X = \{X_1, X_2, X_3, \dots, X_k\} \subseteq N$ such that the pairwise distance between any two points in $X$ is at least $D$, and $\sum_{i=1}^k \mathit{Weight}(X_i)$ is maximized.

It would be nice if I could get the exponential solution and then an efficient heuristic so that I can relate to why and how the problem reduces. The greedy way to do it would be to sort the points by weight and exclude points which are at distance $D$ from the current point that is being processed. Is there a better way to do it?

Answer 1

This problem is a variation of the Maximal Independent Set (MIS) problem in graph theory. To understand that you need to convert your point set $N$ into a graph $G=(N,E)$, where any two vertices $N_1,N_2 \in N$ are connected by an edge if and only if the distance between $N_1$ and $N_2$ is less than the threshold $D$. So the set $X$ you are looking for will be one of independent sets in the graph $G$. However your case is different, because here:

• Each vertex in $G$ has a numerical weight, and you are trying to maximize the total weight of the independent set instead of its size - this problem is called Maximal Weighted Independent Set (MWIS) problem.
• You are looking for an optimal independent set with exactly $k$ vertices.

There is a number of approaches to this class of problems, for example - this one. You can try to adapt their approach to your case with fixed size of the optimal independent set (which might not exist).

Another approach to this problem uses the fact, that the graph $G$ belongs to a class of Unit Disk Graphs. There is a number of approximation algorithms, developed for the MWIS, which use geometric specifics of such graphs - for example, this one. Again, they don't limit a number of vertices in the solution set. General discussion of heuristics for problems on unit disk graphs can be found here.

As for the straightforward heuristic algorithm for MWIS with predefined size of the solution - your approach is correct. I'll describe it in more details here. At first a definition:

• An anti-neighborhood $A(N_i)$ of any point $N_i \in N$ is a subset of $N$, such that for any point $N_j \in A(N_i)$ the distance between $N_i$ and $N_j$ is greater or equal than $D$.

We'll assume that each anti-neighborhood is represented by a tree-like data structure, which can perform three operations:

• Build a set from a list of points in $O(n\log n)$ time.
• Find a point (in the set) with maximal weight in $O(1)$ time.
• Compute intersection of two sets in $O(n\log n)$ time.

So, the algorithm:

Step 1. Find point $X_1$ with maximal weight and build its anti-neighborhood $A(X_1)$.

Step 2. Find point $X_2 \in A(X_1)$ with maximal weight and build the intersection $A(X_1) \cap A(X_2)$.

...

Step $m$. Find point $X_m \in \bigcap_{i=1}^{m-1}A(X_i)$ with maximal weight and build the intersection $\bigcap_{i=1}^{m}A(X_i)$.

...

The intersection of anti-neighborhoods may become empty at some step - in this case the problem doesn't have a solution.

The total time of this algorithm will be $O(kn\log n)$. It's unclear how close this heuristic solution will be to the optimal one.