# How do I assign homes to hospitals based on locality? (clustering, kmeans?)

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?

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