0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
1
$\begingroup$

The stable roommates problem is to find a perfect matching in a non bipartite graph which is "stable". "Perfect" means that every one is assigned to a pair. "Stable" means that it does not exist 2 persons which would prefer to be together instead of their assignement. Note that the stable roommates may have no solution.

Now about your problem, the point is to define the "stable" statement on groups of 6 or 8. And as you said, you want to maximize the global affinity score which is quite different from looking for a stable situation.

Globally your problem is a "graph partition" which is NP-complete, and there is no "efficient" way to find a solution better than try all combinations. Some heuristic algorithms can provide very good results nevertheless.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – David Richerby Jun 27 at 17:32
  • $\begingroup$ @DavidRicherby you are right about that, thanks for the precision. $\endgroup$ – Vince Jun 27 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.