1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This sounds very different to matchings. Why do you think that matchings are the right starting point? $\endgroup$ – David Richerby Aug 18 '17 at 14:16
  • $\begingroup$ just said matching since we are matching "students" to "professors" (except its not 1:1 and there is a min constraint). If you can suggest an alternative way to think about it sure. $\endgroup$ – dg428 Aug 18 '17 at 17:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi, thanks for the response. Can you point me to some of the algorithms you mentioned? I saw Cycle Canceling Algorithm, but not sure if that fits my use case. $\endgroup$ – dg428 Aug 19 '17 at 11:10
  • $\begingroup$ @dg428, see edited answer; I added to the first sentence a link where you can learn more. $\endgroup$ – D.W. Aug 19 '17 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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