1
$\begingroup$

I am looking for an algorithm to split a large team into standup groups so that everyone talks to everyone once a week. We want small groups so the standup doesn't take an hour.

Lets assume we have a large team of 14 (n) people, and we want to split it into 2 (m) teams, and we have 5 (d) days of stand-ups in the week.

How to split this team into groups such that everyone on the team has a shared standup meeting with everyone else at least once a week, or even twice? That is, the groups can change every day of the week, but the optimization criteria is that the number of shared standups between two people is minimal.

I think the solution is related to subsets and combinatorics, but I'm not sure even where to start...

$\endgroup$
  • $\begingroup$ I originally posted this here but was told ask here. $\endgroup$ – Mala Aug 26 '16 at 18:23
3
$\begingroup$

This is what is called a "design theory" question.

I don't have a general answer, and sometimes general answers are hard to come by in design theory.

For the base case $(n=14,m=2,d=5)$:

Label the participants with numbers 0-15. (We can do this with 16 people.)

Have each person write their number in binary, as a 4-digit set of numbers.

On days $k=1-4$, each person looks at the $k$th bit of their number, and groups with the eight people who have the same bits.

At the end of four days week, each person $n$ has paired with every other person other than $15-n$.

On the last day, pick one group as $\{0,1,2,3,12,13,14,15\}$ and the complement for the other group. Now everybody has met with everybody else at least once.

If $k$ is the minimum number of times you want the people to meet, and you have that $n$ is a multiple of $m$ and you want to split each day into $m$ groups of $n/m$ people, exactly, then you need:

$$k\binom{n}{2}\leq dm\binom{n/m}{2}$$

Or:

$$k(n-1)\leq d(n/m-1)$$

Again, for example, with $(m,n,d)=(14,2,5)$, this shows the maximum value of $k$ you might achieve is $k=2$.

This condition is necessary, but not sufficient.

It's much harder if you allow splits into groups of unequal size (and I'm not even sure if that is called design theory anymore.) On some level, if you allow groups of size $1$ and large groups, you can probably solve this general case, but presumably, you want so restriction on the size of the groups to be ideal.

$\endgroup$

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.