Distribution of resources from providers to maximum number of receivers

Question

Consider there is a city with $n$ residents who are in need of internet and there are $m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what providers are available to him. Formally let resident $i$ has list of providers $a_i$. Also each provider has a maximum number of connections he can give, that is, provider $i$ can have at max $k_i$ connections. Find the optimal way of providing internet so that the number of residents having internet is maximum.

My thoughts on the question is that this question looks like a derivative of knack-pack problem with constraints, which suggests dynamic programing but i am unable to find the states. Could anyone help me?

Answer 1

This problem is a case of maximum flow problem.

Suppose we are given internet providers $p_1, p_2, \cdots, p_m$ and residents $r_1, r_2, \cdots, r_n$. Consider a flow network specified as the following.

• Nodes are $s,\ p_1, p_2, \cdots, p_m,\ r_1, r_2, \cdots, r_n,\ t$, where $s$ and $t$ are two extra nodes standing for the source and the sink.
• There is an edge between $s$ and each $p_i$ with capacity $k_i$.
• There is an edge between $p_i$ and $r_j$ with capacity 1 if $p_i$ can provide internet to $r_j$.
• There is an edge between each $r_j$ and $t$ with capacity 1.

What we want is to find the maximum flow from $s$ to $t$.

There are many algorithms to solve a maximum flow problem in polynomial time. For example, Ford–Fulkerson algorithm and Dinic's algorithm are pretty popular. Source code that implement those algorithms in various programming languages can be found easily.

All those algorithm will produce an integral maximal flow, so we will not worry in case the computed maximal flow stipulates that some provider should provide 0.42 or $\frac{\sqrt2}2$ internet to some resident. You can check the integral flow theorem.