Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair has a weight, and I want to maximize the total weight. Equivalently, I have a weight function on $K\_{n,cn}$, and I want to cover it with $n$ copies of $K\_{1,c}$ so that the total weight is maximized.


Of course, if $c=1$ then this can be solved efficiently by (for instance) the Hungarian algorithm. What about $c>1$? I can figure out the dual problem (in analogue to a weighted cover), and am curious whether it is possible to modify the Hungarian algorithm to solve this problem, efficiently or otherwise. It seems like the kind of problem that someone has thought about before, but I have not been able to locate anything on it (maybe because I'm not sure what it would be called).



A modified bipartite assignment problem
Edit: Creating $d$ copies of each advisor and running the standard weighted matching algorithm solves this, if I'm not missing something.


If I understand your question correctly, this is an instance of [Minimum-cost flow problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem), which can be solved in polynomial time by linear programming.


The capacities determine that each advisor should get $d$ students and the edge costs are the compatibility of advisor and students.


