Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that nobody shares a table with the same person twice. Typical values are $|S|=45$ and $k=5$ and 6 to 10 meals.

Put in a more abstract way, I'd like to find a sequence of partitions of $S$ such that each partition consists of pairwise disjoint subsets of cardinality $k$ and the added global property that any intersection between two such subsets contains no more than one element. I suspect this can be formulated as a graph theoretical or combinatorical problem.

I'd be grateful for a better formulation of the problem and pointers to relevant literature as it is outside of my domain.

The background: this could be used for seating arrangements at Schloss Dagstuhl where many computer scientists come to discuss their research over the course of a week. Currently seating is done randomly and unsurprisingly some people find themselves sitting with the same people twice (or more often) over the course of a week. Also unsurprisingly, we receive some complaints about this and vague suggestions how to improve this. I'd like to understand this better. A stronger formulation of the problem involves optimizing who is sitting next to each other but I believe this is not relevant for tables of size 5.

Outside of the application I think the interesting question is for the maximum number of meals that can be served for a given $S$ and $k$, i.e., how many such partitions exist.

share|improve this question
    
IIRC, this sounds like the Hamilton-Waterloo problem. –  Juho Feb 16 '13 at 19:53
    
From glancing at a paper about the Hamilton-Waterloo problem I get the impression that it deals with the stricter problem of ensuring that a participant sits next to each other participant exactly once. –  Christian Lindig Feb 16 '13 at 21:34
2  
+1 for the question, especially since I'll be there in two weeks :) –  Suresh Venkat Feb 17 '13 at 1:34
1  
Kirkman's schoolgirl problem seems to be of similar nature and might be a starting point. –  Christian Lindig Feb 18 '13 at 15:58
add comment

5 Answers 5

up vote 11 down vote accepted

Here's a variant of the original answer (below) that gives the desired setting: tables of size 5, 45 people, and 10 meals, except that one meal has a few tables of size 4.

Let $F$ be the field of size 9. Pick 4 vertical, degenerate lines $\{(b,x) | x \in F\}$ for every $b = 0,1,2,3$ and declare their people "empty." We are left with 81 - 9x4 = 45 people.

9 meals are given by slopes $a = 0,1,\ldots,8$. The intersections with the 4 empty degenerate lines reduce the table size to 9-4=5.

An additional meal is given by the remaining degenerate lines $\{(b,x) | x \in F\}$ for every $b = 4,5,6,7,8$. Here the table size is 9. However (in any solution) we can break a table of size 9 into a table of size 5 and one of size 4.

If there are a few more people one can use the field of size 11.


First let us handle $k^2$ people and $k$ meals.

Pick a finite field $F$ of size $k$ and identify people with $F \times F$. To each meal there corresponds a slope, to a table a line parallel to that slope.

Specifically, meal $a$ has $k$ tables $\{(x,ax+b) | x \in F\}$ for every $b \in F$.

The intersection property you want is the fact that lines with distinct slopes intersect in exactly one point.


To handle $2k^2$ people, divide them up in two groups of $k^2$ each, and apply the construction above to each group. To handle $2k^2 - k = 45$, label (in the first group) a fixed line such as $\{(x,x)|x\in F\}$ as "empty." You may have a few tables with $k-1$ people.

For more meals one could e.g. pick a different partition in two groups at the beginning of the 6th meal. (Say you interleave the original partition, to ensure that the two groups "mix.") Though of course this may result in some intersections.

share|improve this answer
    
This is an interesting construction but too limiting for my particular case because of $|S|=k^2$ but could server as a lower limit. –  Christian Lindig Feb 17 '13 at 20:29
    
I have edited the question to address more general parameters. –  Emanuele Viola Feb 17 '13 at 21:46
1  
I believe that [block design] (en.wikipedia.org/wiki/Block_design) is the appropriate framework for the general case, as pointed out by domotorp below. However, I like the constructive aspect of this and accept is as a good answer. –  Christian Lindig Feb 19 '13 at 9:06
3  
I am curious if a solution with 10 meals exists; I did some googling but couldn't find an answer. Anyway, once the best solution has been found, what about coding it up so that organizers can paste partecipants' names and get back all seats assignments? Would that be useful to them? If we make this simpler other workshops may adopt this nice tradition of Dagstuhl. –  Emanuele Viola Feb 19 '13 at 14:43
1  
Nice update. We should drink a beer at Dagstuhl in your honor if this gets implemented :) –  Suresh Venkat Feb 22 '13 at 4:25
show 3 more comments

Here's a (loose?) upper bound on the number of meals you can serve.

Let $|S| = n$ and assume that $n$ is divisible by $k$. Also, assume that you have exactly $n/k$ tables and you want each table to be full during each meal.

For each meal, construct a graph with a node for each person in $S$ and an edge when two people share a table. This graph is a collection of $n/k$ cliques each of size $k$. Thus the number of edges in the graph is $\Theta(nk)$.

Since you don't want any edge to occur in two different meals, and since the total number of edges possible on a vertex set of size $n$ is $\Theta(n^2)$, this shows you can only serve $O(n/k)$ meals.

Actually, it's not difficult to find the constants here and when you do the math, you get an upper bound of exactly $\frac{n-1}{k-1}$, which, for your typical values, is 11.

share|improve this answer
add comment

If you want any two people to sit at the same table exactly once, then this is called a resolvable 2-design and has been studied a lot. Of course allowing to skip a few meals would give a solution to your problem when two people can meet at most once. (But other solutions might exist, I suppose.)

share|improve this answer
    
I would like two people to meet at most once. The identity of the table is not an issue and I'm not sure about the significance of to sit at the same table as part of your answer but will look up the linked definition. –  Christian Lindig Feb 18 '13 at 14:01
add comment

I'm not sure if you require a deterministic algorithm, but I've solved a similar problem in the past using a Markov chain Monte Carlo method.

You can see a working example of this approach on Github - this program attempts to seat a group of people at tables of a fixed size, given a set of seating constraints which may be either positive or negative ("must" or "must not"), and either absolute or relative ("preferable").

Note: this program doesn't solve exactly the same problem that you propose, but it does give a working demonstration of a Markov chain Monte Carlo method, and it's close enough that you can easily adjust it as needed for your problem.

The program solves the problem for one dinner, but in your case, an easy way of approaching the problem would be to run the algorithm once for each dinner, each time providing each diner's previous companions as either fuzzy or absolute negative requirements. (The advantage of fuzzy requirements is that you are guaranteed that the algorithm will halt on all inputs, even if a perfect arrangement cannot be found).

In this process, we would first attempt to seat each diner according to the absolute requirements - you may want to skip this part of the process, since it only works when the absolute requirements are relatively small in number; otherwise you end up with an incredibly huge problem!

In the next step, we create a series of tables and randomly assign participants to the tables for an initial configuration, and a score is calculated to represent the number of fuzzy requirements that have been satisfied. Pairs of diners are randomly switched, and the score is recalculated for those tables to determine whether the new configuration is preferable.

This part of the process should ideally be repeated with several initial configurations, and can easily be computed in parallel.

share|improve this answer
    
Interesting and +1 for showing us code. I thought about randomly drawing table configurations and trying to iterate on those where collisions happen. Simulated annealing came also to mind. For my particular case it would be even enough to pre-compute configurations for various $|S|$. –  Christian Lindig Feb 17 '13 at 20:32
add comment

I think any valid seating arrangement is equivalent to a d-regular hypergraph on |S| vertices, where d is the number of dinners, with rank at most k and maximum codegree 1. The trivial solution is to have everyone always sit by themselves, but I guess the goal is to minimize the number of tables?

share|improve this answer
1  
The number of tables is fixed in this setting. And it's strictly less than the number of people. –  Suresh Venkat Feb 18 '13 at 3:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.