I have a large set of $(X)$ hospitals and $(Y)$ homes, where $(Y)$ is much larger than $(X)$, and their respective coordinates. Each hospital can handle any home within a 50 mile radius, and up to 10,000 homes. Homes can be assigned to one hospital. How do I create assignments of homes to hospitals such that as many homes can be assigned a hospital? Performance doesn't matter that much.

I was thinking of potentially getting each hospital to do a breadth first search to reach as many homes as possible near it. For this, I was thinking of calculating the distance to all homes from each hospital, then going through each home and matching with the nearest hospital until all homes are filled or can't be any more.

Would this be a good approach? What would a better approach be? Are there clustering algorithms that could help here such as kmeans?

  • $\begingroup$ Can you please give an estimate on $|X|$, $|Y|$ and on the average number of houses reachable from a hospital? $\endgroup$ – Dmitry Feb 25 at 22:29
  • $\begingroup$ It seems like a verb might be missing in "as many homes can be assigned a hospital"? $\endgroup$ – D.W. Feb 26 at 0:40
  • $\begingroup$ Integer linear programming might be a fine solution for this problem, too. $\endgroup$ – D.W. Feb 26 at 0:43

Construct a graph $G=(V,E)$ where $V$ contains two nodes $s$ and $t$, a node $u_x$ for each hospital $x \in X$, and a node $v_y$ for each home $y \in Y$.

There is an edge between $s$ and each $v_y$ of capacity 1. There is an edge of capacity $10000$ between each $u_x$ and $t$. Moreover, there is an edge $(v_y, u_x)$ if an only if $y$ is within $50$ miles from $x$. Edges $(v_y, u_x)$ have unbounded capacity.

Compute a maximum flow $f$ from $s$ to $t$. The value $|f|$ of the flow tells you the maximum number of homes that can be assigned to some hospital. Moreover, $f$ itself tells you a possible assignment: assign $y \in Y$ to $x \in X$ if and only if $f(v_y, u_x)=1$.

  • $\begingroup$ Well, it’s a bit infeasible for large inputs. That’s why I’ve asked for more precise information about the data. $\endgroup$ – Dmitry Feb 26 at 12:49
  • $\begingroup$ It seems plausible that the graph will be sparse if the data comes from the real world. There probably aren't too many hospitals in a 50-miles radius, so the out-degree of each vertex will be small. Maybe the OP can give us an estimate of the number of hospitals near each house in their data. $\endgroup$ – Steven Feb 26 at 13:27
  • $\begingroup$ It's actually almost surely infeasible if the data is real-life and if apartments in buildings are considered to be homes. E.g. the radius of the entire New York is something like 20 miles, so every hospital covers every house there $\endgroup$ – Dmitry Feb 26 at 13:42
  • $\begingroup$ I see. However in that case, all apartments that can be served by the same set of hospitals can be merged together into a single house $y$. The capacity of $(s, v_y)$ is the number of merged apartments. $f(v_y, u_x)$ tells you how many of the merged apartments (which can be picked arbitrarily) need to be assigned to hospital $x$. $\endgroup$ – Steven Feb 26 at 13:50
  • $\begingroup$ I agree. Didn't think that density can also help us. Let's wait for clarifications from OP. $\endgroup$ – Dmitry Feb 26 at 13:53

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.