Algorithm for seating groups of people?

views:

174

answers:

+4 Q:

Algorithm for seating groups of people?

I'm interested in writing an application that can determine how to seat groups of 2-10 people at tables that can hold 10 people. There will probably be about 15 tables and 140 people total. I don't want to break up any of the groups of people.

It seems like it might be a common problem and I was wondering if anyone had any suggestions on where I should start to look for a solution to this. Any links or suggestions appreciated.

Let the groups decide where to sit. Is it okay if the groups decide on their own to break up, merge with other groups, or move tables together?

mcandre 2010-07-07 14:26:00

James Curran 2010-07-07 14:28:05

No it's too big for that, if I let them decide groups usually get broken up.

Abe Miessler 2010-07-07 14:30:26

Distribute the biggest groups first, then add smaller groups wherever you can.

mcandre 2010-07-07 14:31:34

+1 A:

This is just a variation on the standard "Knapsack problem"

James Curran 2010-07-07 14:26:18

No it is not! Knapsack has pseudo-polynomial solutions while bin-packing does not.

Moron 2010-07-07 14:53:16

When we had this problem in school we solved it with as a TSP problem.

Marcus Johansson 2010-07-07 14:28:54

That means that the problem is NP-hard. So Abe will probably not find an optimal algorithm...

YuppieNetworking 2010-07-07 14:33:08

@Yuppie: No, that means it's NP, which doesn't really tell us anything *(though the fact that you modeled the problem as TSP in class rather than using a polynomial-time algorithm hints that the instructor knew the problem is NP-complete :)*

BlueRaja - Danny Pflughoeft 2010-07-07 16:13:22

+10 A:

This is the bin packing problem.

Svante 2010-07-07 14:29:50

@Abe Miessler, check out this link and read about the _First-fit algorithm_. The general problem is hard, but your size limits make it easy to do with the naive, greedy approach.

grossvogel 2010-07-07 14:38:13

The size limit makes it easy if it is underspecified -- meaning there are many solutions. However, in the other extreme case where it is impossible to seat all groups at ten tables (but just barely), you have to exhaust every possibility to determine that it is impossible.

orangeoctopus 2010-07-07 14:43:44

AFAIK, the first-fit approach is what most filesystems and memory managers use when allocating space, and it works quite well.

rmeador 2010-07-07 16:08:35

This is the bin packing problem, which is NP-Hard (it's not easy to find the best answer, and it's not easy to check if an answer is the best).

The groups of people are an individual objects, with the volume = the number of people people in the group. The tables are the bins of size 10.

There are a few approximation algorithms out there, which should be easy to find knowing that you should google for bin packing.

However, your problem is relaxed (in some ways) because you have 10 tables -- i.e., you are not trying to fit the people on the minimum number of tables. If 10 tables is the OPTIMAL solution, you will have trouble finding the solution (if it even exists), but if the optimal is really 7 or 8, finding the solution will be easy. It all depends on the group distributions.

orangeoctopus 2010-07-07 14:33:49

The optimal can't be 7 or 8 as there are ~140 people and table size is 10.

Moron 2010-07-07 15:05:19

ansaurus

tags:

views:

answers:

Algorithm for seating groups of people?

related questions