Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



restaurant seating problem
Posted:
Jul 17, 2011 10:57 PM


I would like to know the status of the following problem in terms of whether or not there a polynomially bounded time solution. Actually this is a family of problems, one for each value of s defined below.
Problem: A restaurant wishes to use as few tables as possible to seat a group of n people. Some pairs of people refuse to be seated together so to seat k people at a table requires that the graph of people willing to sit together implies the k people form a clique. A table is considered used if at least one person sits at the table. It is not a requirement that each used table be filled. Each table in the restaurant seats at most some constant number s people.
What is the complexity of finding a solution for this problem for a given value s.
Note that if each table seats 2 people (s=2) then the problem is reducible to maximum matching and thus is solvable in polynomial time.
I have no doubt that for sufficiently large s the decision version of this problem is NPComplete. But what is the smallest value of s for which NPCompleteness results?
For s = 3 I have ideas that might (but probably not at this early stage) lead to a polynomially bounded solution. For s >= 4 I have no insights at all.
Ideas welcome. References welcome. Pointing me to other groups more appropriate for this question welcome.
Finally, are there practical applications to this problem, especially for the case of s = 3 since I will continue to explore a polynomially bounded solution for this case.
If you want to email me directly, my email is rpboland@gmail.com
Regards,
Ralph Boland



