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/