We have N workers and they should be assigned to one of M teams. Each team can have a maximum of K workers. Each worker ranks the teams in order of preference, starting from 1 for the most preferred team to M for the least preferred team. Now the problem is to find a matching, so that workers end up in the team they prefer most, given the constraint that each team can have a maximum of K workers.
At first I thought, this is an Assignment problem that could be solved using the Hungarian Algorithm. But then I realised that the Hungarian Algorithm can only be used if each worker is assigned to exactly one item. But in my case several workers can be assigned to the same team.
Now I'm unsure what kind of problem this really is. Is this a (multiple) Knapsack problem or Bin packing problem ? What kind of algorithm could I use to solve that problem?
There are two ways to address this problem, and which is the more efficient one depends on how many people and how many teams you have, and how large K is.
The easier way (which is already mentioned in @Alex L.'s answer) is to split each team into K teams, and convert the problem into regular weighted bipartite matching, that can be solved with hungarian algorithm. Now, the complexity of the hungarian algorithm is O(n^2 * m). Here we would choose n to be the number of people, and m to be the number of teams. After we split each team into k, the final complexity will be O(n^2 * m * k).
Another way is to treat this problem as a min-cost max-flow problem. You construct a graph with a source and a sink being two extra nodes, all the workers directly connected to the source with capacity 1 and weight 0, all teams connected to the sink with capacity k and weight 0, and workers connected to teams with capacity 1 and cost depending on their preferences. Min-cost max-flow has complexity O(n^3 * m). Now, if we choose number of workers to be n and number of teams to be m, we get something which is strictly worse than hungarian (because presumably k < n). But if we take n to be number of teams, and m to be number of workers, we can potentially get something better than hungarian, if number of workers is large, number of teams is small, and k is large as well.
So it all depends on your constraints. If m is significantly smaller than k and n, you are better off with min-cost max flow, otherwise just split teams into k and use vanilla hungarian algorithm.