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?

  • $\begingroup$ 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$. $\endgroup$ – Steven May 17 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)$.

| cite | improve this answer | |

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.