<p>This is sometimes known as the <a href="http://www.cs.brown.edu/~sello/golf.html" rel="nofollow">Social Golfer</a> problem (see also <a href="http://mathworld.wolfram.com/SocialGolferProblem.html" rel="nofollow">the Wolfram MathWorld page</a> and <a href="http://www.csplib.org/prob/prob010/index.html" rel="nofollow">this page from CSPlib</a>). Probably the most famous instance of this problem is <a href="http://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem" rel="nofollow">Kirkman's Schoolgirl problem</a>.</p>

CC BY-SA 3.0
2011-04-15T21:31:42.420Z
2011-04-15T21:31:42.420Z
mhum
<p>We have <em>n</em> people and split them up in groups of size <em>x</em>. Each group of <em>x</em> 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.</p>

<p>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 <em>x</em> vertices each and minimize the sum of the edges connecting the vertices in each subgraph.</p>

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

CC BY-SA 3.0
2011-04-13T06:13:29.173Z
You might want to read about block designs: http://en.wikipedia.org/wiki/Block_design
Karolina Sołtys
CC BY-SA 3.0
2011-04-13T08:11:55.157Z
Your problem seems to be a more complicated variant of what is called the "Oberwolfach problem".
5501
<graph-theory><co.combinatorics><optimization>
Sending people to lunch together with minimal repetition
ajmurmann
# Sending people to lunch together with minimal repetition

(Asked by: username_0 on 2011-04-13)

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?

**Tags:** graph-theory, co.combinatorics, optimization

> **Comments:**
> **username_1**: You might want to read about block designs: http://en.wikipedia.org/wiki/Block_design  
> **username_2**: Your problem seems to be a more complicated variant of what is called the "Oberwolfach problem".  

---

## 1 answers

### Answer by username_3 on 2011-04-15. Score: 3

This is sometimes known as the [Social Golfer](http://www.cs.brown.edu/~sello/golf.html) problem (see also [the Wolfram MathWorld page](http://mathworld.wolfram.com/SocialGolferProblem.html) and [this page from CSPlib](http://www.csplib.org/prob/prob010/index.html)). Probably the most famous instance of this problem is [Kirkman's Schoolgirl problem](http://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem).


---

