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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.