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