Divide people into teams for most satisfaction

Question

Just a curiosity question. Remember when in class groupwork the professor would divide people up into groups of a certain number (n)?

Some of my professors would take a list of n people one wants to work with and n people one doesn't want to work with from each student, and then magically turn out groups of n where students would be matched up with people they prefer and avoid working with people they don't prefer.

To me this algorithm sounds a lot like a Knapsack problem, but I thought I would ask around about what your approach to this sort of problem would be.

EDIT: Found an ACM article describing something exactly like my question. Read the second paragraph for deja vu.

Answer 1

To me it sounds more like some sort of clique problem.

The way I see the problem, I'd set up the following graph:

• Vertices would be the students
• Two students would be connected by an edge if both of these following things hold:
  1. At least one of the two students wants to work with the other one.
  2. None of the two students doesn't want to work with the other one.

It is then a matter of partitioning the graph into cliques of size n. (Assuming the number of students is divisible by n)

If this was not possible, I'd probably let the first constraint on the edges slip, and have edges between two people as long as neither of them explicitly says that they don't want to work with the other one.

As for an approach to solving this efficiently, I have no idea, but this should hopefully get you closer to some insight into the problem.

Answer 2

You could model this pretty easily as a clustering problem and you wouldn't even really need to define a space, you could actually just define the distances:

Make two people very close if they both want to work together. Close if one of them wants to work with the other. Medium distance if there's just apathy. Far away if either one doesn't want to work with the other.

Then you could just find clusters, yay. Then split up any clusters of overly large size, with confidence that the people in the clusters would all be fine working together.

Answer 3

This problem can be brute-forced, hence my approach would be first to brute force it, then fix it when I get a better idea.

Answer 4

There are a couple of algorithms you could use. A great example is the so called "stable marriage problem", which has a perfect solution. You can read more about it here:

http://en.wikipedia.org/wiki/Stable_marriage_problem

The stable marriage problem only works with two groups of people (men/women in the marriage case). If you want to form pair you can use a variation, the stable roommate problem. In this case you create pairs but everybody comes from a single pool.

But you asked for a team (which I translate into >2 people per team). In this case you could let everybody fill in their best to worst match and then run the