# Sending people to lunch together with minimal repetition

We have n people and split them up in groups of size x. Each group of x people goes to lunch together. Next time around when the groups are set up people who were in a group last time should not end up in a group together if avoidable. Ideally they also should go out with as few people from the time before that.

I thought about modelling this as a graph problem: People are vertices $v \in V$ and going to lunch together creates a edge between those vertices. The edge has a weight on it that's higher the more recent the lunch happened. Now we want to create $\frac{|V|}{x}$ subgraphs with x vertices each and minimize the sum of the edges connecting the vertices in each subgraph.

Is there a name (lunching programmers ? ;-) ) and associated research for this problem? Or is there a way to map this to another known problem?

• You might want to read about block designs: en.wikipedia.org/wiki/Block_design – Karolina Sołtys Apr 13 '11 at 6:13
• Your problem seems to be a more complicated variant of what is called the "Oberwolfach problem". – 5501 Apr 13 '11 at 8:11