Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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 NP-Complete.
But what is the smallest value of s for which NP-Completeness
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
|
|
|
|
