Associated Topics || Dr. Math Home || Search Dr. Math

### Optimal Seating Arrangements

```
Date: 07/20/2000 at 11:03:38
From: Ben Schwartz
Subject: Optimal Solution for a Requested Seating Arrangement

My mother encountered this problem when she was planning large
parties. N people are invited, and their invitations ask them to RSVP
with the names of up to k people they would like to sit with. Is there
a formula or method that can be applied here, given a table size s, to
yield the "best" arrangement of people?
```

```
Date: 07/20/2000 at 16:31:48
From: Doctor Rob
Subject: Re: Optimal Solution for a Requested Seating Arrangement

Thanks for writing to Ask Dr. Math, Ben.

There is no formula or algebraic method to figure out the best
arrangement. The way to proceed is to do what is called a discrete
hill climb.

I assume that N is a multiple of s, so there are no empty places at
any of the tables.

Start with a random arrangement of people at the tables. Compute a
score for this arrangement. I would probably make the score be the sum
over all individuals of the number of people at his table that he
requested divided by the total number he requested. That would
represent the fraction of his request that was accommodated, and could
be a measure of his satisfaction. If he got 1 of the 3 people he
requested, then he is 1/3 satisfied. The score would be the total of
these satisfaction fractions over all people. (Other score functions
are also possible, and maybe even desirable.)

Then try all possible swaps of two people from the current
arrangement, score those outcomes, and do the one (or one of those)
that gave the largest increase in the score. Continue this over and
over until the score can't increase any more. Record the setup and its
score.

Choose a new random starting arrangement, and repeat this process.
After several hundred such choices, pick the arrangement you have
recorded with the highest score.

This may not get you the theoretically best arrangement, but it will
be close to the best.

Note that you needn't recompute the entire score function, only the
terms that involve the two swapped individuals.

Programming this is not too tough. You could do it in any language
with which you are familiar: C, C++, FORTRAN, Mathematica, or even
BASIC. The program will be a bit long, but nothing tricky is involved.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search