Weighted Matching with multiple assignments and min assignments

Question

I need to do a weighted matching between two sets (say students and professors). The set of students is much larger than set of professors. So multiple students can be matched to professors. However, each professor also has a minimum number of students he needs. So even though all students maybe matched best with one professor, some need to distributed amongst the rest, as long as they can be matched of course -- since not all professors and students will have edges between them.

Standard Bipartite matching won't work since they match one to one. Max Flow won't work since they don't consider weights.

Answer 1

Your problem can be solved with minimum-cost network flow, by solving a circulation problem. The circulation problem is a variation on network flow where edges have an upper bound on the amount of flow through that edge (called the capacity of the edge), a lower bound on the amount of flow through the edge, and a per-unit cost for sending flow through the edge. In your problem, you have a source vertex $s$, a vertex $v_i$ for each professor, a vertex $w_j$ for each student, and a sink vertex $t$. You have edges $s \to v_i$, $v_i \to w_j$, and $w_j \to t$. You put a lower bound on the edge $s \to v_i$ corresponding to the number of students who professor $i$ must be matched with, an upper bound of $1$ on each edge $v_i \to w_j$, and a cost on the edge $v_i \to w_j$ that corresponds to the negative of the weight. There exist polynomial-time algorithms to solve this variant of network flow.