2
$\begingroup$

I have the following problem:

In a school, there are n students and m clubs, with n > m. Each student needs to be assigned a club. The students have preferences, (say top 3 or top 5) of the clubs they wish to be matched to. So far, it's basically just a maximum weight matching in a weighted bipartite graph, which can be done through the Hungarian algorithm.

But now the constraint is that there's both a maximum and a minimum number of slots that each club can accommodate. A way to deal with the maximum constraint would be to have multiple copies of each club, one for each slot, and then run the Hungarian algorithm to calculate the maximum weight matching as before. However, we also want a minimum number of students in each club, say to make the club functional - and this number can be different for different clubs based on popularity. Is there any way to do this? Would it mean a tweak to the main algorithm, or perhaps just a post-algorithm shuffling?

$\endgroup$
0

0

Browse other questions tagged or ask your own question.