Find Best N Points From a Graph

Question

I've given a task and wonder if there are any better solutions.

Inputs of task are:

1. Distance of district pairs

2. Population of pairs

Goal is:

• Find n districts at which its population and districts x miles range districts' population is max.

Extra information:

• Unique district size is tens of hundreds.

As an example, if I pick up district A, population will be A's population plus other districts' population which are less than x miles far away from it. Total population will be n districts at which population is calculated as I mentioned.

What I've tried:

1. Brute Force
2. Generic Algorithms

What I planning to do:

1. A* Search

My question is, there may be any other solution (optimal if possible) instead of these one. i.e. sorting districts by their population, merging x miles nearest to them into one until I get n districts.

Any ideas?

Answer 1

If I understand the problem correctly, there is no polynomial-time algorithm that finds an optimal solution to your problem unless $\mathsf{P}=\mathsf{NP}$. This holds even in the special case in which all distances are $1$, all populations are $1$, and $x=1$.

To see this notice that, given a graph $G=(V,E)$ and a non-negative integer $n \le |V|$, $G$ admits a dominating set of size at most $n$ if and only if there is a set $S \subseteq G$ with $|S| = n$ such that $\sum_{u \in V : d(u, S) \le 1} 1 = |V|$.

On the bright side, a simple greedy algorithm has an approximation ratio of $\frac{e}{e-1} < 1.582$: iteratively add to $S$ the district $v$ that maximizes the population that falls within distance $x$ of $S \cup \{ v \}$, i.e., the quantity $\sum_{u \in V : d(u, S \cup \{v\}) \ge x} p(u)$.

The approximation ratio of the above algorithm follows from the fact that you can cast your problem as a weighted maximum coverage problem. In this problem you have a set $X$ of elements and a collection $\mathcal{S}$ of subsets of $X$. Each element $v \in X$ has a non-negative weight $w(v)$. You are given an integer $k \le |S|$ and you want to select a subset $S$ of at most $k$ sets of $\mathcal{S}$ such that $\sum_{x \in \bigcup_{S' \in S} S' } w(x)$ is maximized. To reduce your problem to weighted maximum coverage problem pick $X=V$, $\mathcal{S} = \{S_v \mid v \in V\}$ where $S_v = \{u \in V \mid d(u,v) \le x\}$, $w(v) = p(v)$, and $k=n$

Since you can also reduce any instance of weighted maximum coverage problem to your problem, this is essentially the best polynomial-time approximation algorithm that you can hope for. The reduction is as follows: Create a complete bipartite graph $G = (V,E)$ with $V = \mathcal{S} \cup X$ and $E = \mathcal{S} \times X$. Each edge in $E$ has weight $1$. The population $p(v)$ of a vertex $v \in V$ is $p(v) = 0$ if $v \in \mathcal{S}$, and $p(v) = w(v)$ if $v \in X$. Pick $n=k$ and $x=1$. You can easily see that you can restrict yourself to a solution $S$ that does not select any district in $v \in X$ (since $S \setminus X$ is as good as $S$ and $|\mathcal{S}| \ge k = n$). Then, selecting a subset $S \subseteq \mathcal{S}$ of districts corresponds to covering all the elements in $\bigcup_{S' \in S} S' \subseteq X$, and the population within distance $x$ of a vertex in $S$ is exactly $\sum_{x \in \bigcup_{S' \in S} S'} p(x) = \sum_{x \in \bigcup_{S' \in S} S'} w(x)$.