CODEWITHSUNDEEP
algorithmlanguage-agnosticcomputer-science
asmaier
asmaier

Reputation: 11746

Algorithm to assign workers to teams based on workers preferences

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?

Upvotes: 2

Views: 1825

Answers (3)

Ilya Kulshin
Ilya Kulshin

Reputation: 1

This is the stable marriage problem. The base case allows for a 1-1 matching, but it can be easily generalized to allow for a 1-K matching. In the case of 1-K matching, the teams do not need to all be the same size. The teams may also have a preference for some specific workers over others, or may prefer all workers equally.

If the teams have no preference, this amounts to first assigning all the workers to their most preferred team. Then if any team(s) are oversubscribed, spill over the extra workers to their second preferences. Repeat until all workers are assigned.

Upvotes: 0

Ishamael
Ishamael

Reputation: 12795

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.

Upvotes: 2

Alex Libov
Alex Libov

Reputation: 1491

With small adjustment, it can become an Assignment problem:

If you duplicate each team into K teams with capacity of 1 - then you'll need to assign each worker to a team and each team can only be assigned to one worker.

In an Assignment problem the number of agents and tasks doesn't have to be equal.

Upvotes: 1

Related Questions