# Find Best N Points From a Graph

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

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?

• I'm not sure if I understood your problem. Can you confirm that it is the following? You have a non-negatively edge-weighted undirected graph $G=(V,E)$ in which each node $v$ represents a district and is associate with a non-negative integer $p(v)$ that represents its population. You are additionally given two non-negative integers $n$ and $x$. The goal is to find a subset $S$ of vertices of $V$ such that $|S| = n$ and $\sum_{u \in V : d(u, S) \le x} p(u)$ is maximized, where $d(u, S) = \min_{v \in S} d(u,v)$ and $d(u,v)$ denotes the distance between $u$ and $v$ in $G$. May 17, 2020 at 16:19

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)$$.