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?

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

This is sometimes known as the Social Golfer problem (see also the Wolfram MathWorld page and this page from CSPlib). Probably the most famous instance of this problem is Kirkman's Schoolgirl problem.


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.