3
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

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, 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.

$\endgroup$
  • 2
    $\begingroup$ Treating it as a network flow problem (and using an efficient algorithm for that problem) should be more efficient than making $d$ copies of each advisor, especially if $d$ is large. Of course, if you happen to have available a good implementation of the matching problem but not a good implementation of network flow, you might want to go with that. $\endgroup$ – Robert Israel Apr 13 '16 at 21:06
  • $\begingroup$ Mert's simple solution is clearly right (and I can't believe I missed that!) The same idea works for a further generalization I had in mind, in which each advisor has $d$ students and each student has $e$ advisors. $\endgroup$ – Jeremy Martin Apr 14 '16 at 21:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.