Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.research

Topic: restaurant seating problem
Replies: 1   Last Post: Jul 18, 2011 8:21 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Ralph Boland

Posts: 2
Registered: 7/21/09
restaurant seating problem
Posted: Jul 17, 2011 10:57 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.