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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Apr 13, 2016 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
    Commented Apr 14, 2016 at 21:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .