Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/