Maximum Number Of “Teams”

Question

I have a definition for a team of people. I need to find the largest number of teams that I can get based on a list of people (and their applicable slots) given that once a person is "used" for a slot, they cannot be used again.

Simplified Example:

**Team Requirements**
Slot A: 2 People
Slot B: 1 Person
Slot C: 1 Person

**People And Which Slots Are Applicable**
Person 1: A
Person 2: A,C
Person 3: A,B
Person 4: B
Person 5: A,B
Person 6: C
Person 7: C
Person 8: A

Possible Answer

Team 1
A: P1, P8
B: P4
C: P6

Team 2
A: P2, P3
B: P5
C: P7

For my real-world problem, I have multiple slots (1-10 per team) and 1-1000 people that can have up to 20 slots each.

Can anyone recommend an algorithm that fits this type of group optimization problem?

Answer 1

This can be solved by finding a Maximum Cardinality Bipartite Matching in each of a series of graphs, in O(n^2.5 log n) time overall.

To do this, first convert each slot type to a set of the appropriate number of distinct slots, so that we wind up with slots A1, A2, B, C. The final solution will assign a person to a specific slot in a specific team (e.g. Person 3 to slot A2 in Team 1), but we can simply forget the "2" (and also the ordering of the teams, which is likewise purely artificial).

Start by calculating an optimistic estimate k of the number of teams: RoundDown(n/4) will do, since each team uses 4 people, so we can't have more teams than this. Now make 4k vertices in one part of the bipartite graph -- that is, a vertex for each of the 4 slots in each of the k potential teams: A1_1, A2_1, B_1, C_1, A1_2, A2_2, B_2, C_2, ..., A1_k, A2_k, B_k, C_k. In the other part of the bipartite graph, make a vertex for each person. Finally, connect up each person-vertex with all the slot-vertices that they are permitted to fill: So e.g. if a person x can occupy slots A or C, they should be connected by an edge to every slot that begins with "A" or "C" (which would be 6 edges for the example with 8 people).

Then, solve the MCBM problem on this graph, e.g. in O(n^2.5) time by using the Hopcroft-Karp algorithm. The result will be a subset of the edges that can be interpreted as assigning each person to at most one slot in a team, and filling each slot in a team with at most one person. If this results in every slot being filled, hooray! We have a largest-possible number of teams. Otherwise, if there are some team slots left unfilled by any person, reduce the number of teams and try again. (You can reduce the number of teams by 1 each time, which results in a linear number of MCBM problems that need to be solved -- but you can save time by binary-searching. That means starting by halving the number of teams, and thereafter reducing or increasing the number of teams by half the previous amount, reducing when some team has an unfilled position and increasing when none do, until convergence.)