CODEWITHSUNDEEP
algorithmcombinatorics
Lithimlin
Lithimlin

Reputation: 560

Divide n people into m groups k times with minimal overlap

Let's say I have

in a way where everyone meets as many people as possible with as little repetition as possible.

I've tried to do some research on my own but couldn't find anything that sounded like it was what I was looking for.

If you need any more information, just let me know.

Thanks in advance

Upvotes: 3

Views: 2087

Answers (2)

hilberts_drinking_problem
hilberts_drinking_problem

Reputation: 11602

You can frame this as an integer programming problem.

Define a binary variable A[i,g,t] = 1 if person i in N belongs to group g in G at time t in T and 0 otherwise. Then, M[i,j] = sum(A[i,g,t] * A[j,g,t] for g in G, t in T) is 1 iff i and j meet.

Say you want to maximize the number of pairs of people who meet at least once. Then, your objective becomes sum(M[i,j] for i, j in N).

You can express your constraints linearly:

  1. Group sizes are limited: forall g in G, forall t in T, sum(A[i,g,t] for i in N) <= quota[g,t].
  2. Each person is assigned to exactly one group at each period: forall i, forall t, sum(A[i,g,t] for g in G) = 1.

There are several open source solvers that should perform well at your proposed scale.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65427

This is a close variant of the Social Golfer Problem. There's an algorithm due to Triska and Musliu that works well; see https://github.com/FelixHenninger/socialgolfer.js/tree/master for an implementation.

Upvotes: 3

Related Questions