While I do realise pasting an exercise question in here is not exactly perfect form, I am desperate and I wil try anyway. So here it goes:
Consider a set of n mobile computing clients in a town with k mobile base stations. Every client needs to be connected to one exactly one base station. Each of the n clients as well as each of the k base stations is specified by its (x,y) coordinates in the plane. Each client needs to be connected to exactly one base station. For a given parameter r, a client can only be connected to a base station that is within distance r from the client. At the same time, no base station can handle more than L clients being assigned to it. Design a polynomial-time algorithm for the following problem: Given the positions of the n clients and k base stations, as well as the range and load parameters r and L, respectively, decide whether all clients can be connected to the base stations, subject to the range and load conditions as described above. Argue that your algorithm is correct.
I understand that I have to use Max-Flow theory somehow, and I am guessing the flow network would be a bipartite graph with a constraint on the degrees of one of the two partitions to be <= L. But how do I model a positional variable like r into it? Any help would be greatly appreciated.
I am a official tutor in algorithmic graph theory. I’ll save you. :-) We construct a usual flow model $\mathcal F$ for your problem as follows. Let $s$ and $t$ be a sourse and a target, respectively, of a flow network, $c_1,\dots, c_n$ be the clients, and $b_1,\dots, b_k$ be the base stations. Introduce edges $(s, c_1),\dots, (s, c_n)$ of capacity $1$ each and $(b_1,t),\dots, (b_k,t)$ of capacity $L$ each. Also introduce edges $(c_i,b_j)$ iff the distance between $c_i$ and $b_j$ is at most $r$. It is easy to check that all clients can be connected to the base stations, subject to the range and load conditions iff maxflow in $\mathcal F$ is $n$ (one way it is obvious, but the other way we use Integrality Theorem stating that if all capacities are integral, then there is an integral maximum flow). There are the following polynomial-time algorithms to find a maxflow in $\mathcal F$.