2
$\begingroup$

While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the threesome roommates problem, is NP-complete.

However, I'm wondering if there's an approximation algorithm. This is for a specific use case - grouping people into tables for conversation, based on their preferences - and it doesn't need to be perfect.

While it would be interesting to know if such an article has been described in an academic paper, I'm primarily looking for an implementation of such an algorithm (in any language).

An algorithm for a foursome version would also be interesting.

$\endgroup$
3

0

Browse other questions tagged or ask your own question.