# Variant of the “Stable Roommates Problem” when room has not 2 but “n” mates

I'm looking at the name of a variant of the Stable Roommates Problem, when the rooms have more than 2 mates, ie for example 6 to 8. Does this problem has a specific name? A well-known algorithm?

To summarize, the problem is the following: Given a set of $$n$$ people, and a symetric $$n\times n$$ affinity matrix between each person, find an optimal disjoint set partition of the people into $$m$$ groups of a given size, maximizing the global "affinity score" (the sum of each pair affinity in each group).

Why this question? I'm organizing a wedding ceremony with around 60 people, grouping people into tables of 6 to 8. Each person pair has an affinity weight, ranging from $$-\infty$$ (they can't stand each other) to $$+\infty$$ (they better be together).

This question is somehow related, but unfortunatly does not have any answer.

• Your last paragraph is (probably) somewhat inaccurate. For many NP-complete problems, we do know algorithms that are faster than just trying all the combinations. For example, Eppstein has shown that you can determine whether $n$-vertex graphs are 3-colourable in time $O(1.3289^n)$, which is much faster than the brute-force $\Theta(3^n)$. (Plus, we don't know that P and NP are different so, in theory, there could be polynomial-time algorithms for all NP-complete problems anyway.) – David Richerby Jun 27 at 17:32