Jul 24, 2015
Friday
|
02:00 PM - 02:45 PM
|
|
The Banquet Seating Problem
Michelle Rosado (University of Puerto Rico), Ashley Scruse (Clark Atlanta University), Alexis Jane Torre (University of Arizona)
|
- Location
- MSRI: Baker Board Room
- Video
-
- Abstract
Suppose you want to seat n = mk people around k tables with m people at each table. Each person gives you a list of j people next to whom they would enjoy sitting. What is the smallest j for which you can always make a seating arrangement that would seat each person next to one of the people on their list? In this paper we show that j must be strictly more than half of n, the total number of people. Our key tool is a particular ‘blue-green-red’ lemma that helps us construct ‘worst-case scenario’ seating arrangements. We consider cases with two tables and more than two tables and explore seating arrangements with particular kinds of preferences.
- Supplements
-
--
|
|