# Is there an approximation algorithm for the three-person stable roommates problem?

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.

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 roommates version would also be interesting.

• What would count as an approximate solution? One which has a small number of blocking triples? Mar 5, 2021 at 12:23
• I mean an algorithm that will probably yield moderately good results, but which isn't mathematically guaranteed to the best. Here 'good results' means relatively happy people, and happy people are people paired with people they prefer to be with. Mar 5, 2021 at 20:57
• – D.W.
Mar 5, 2021 at 21:01
• What I was trying to get at in my question is what precisely you mean by "good results". When is solution A better than solution B ? When the average rank of the roommates people get is higher (according to their preference lists)? When there are fewer people with low ranking roommates? (what counts as low ranking?) When the number of blocking triples is smaller? (which would be the most natural choice imho, considering the original problem is to find groupings with no blocking triples) This needs to be precisely specified before someone can try to answer the question. Mar 5, 2021 at 21:05
• Thanks for your question! I'm looking for an existing implementation of such an algorithm that is roughly in this ballpark. To me it doesn't matter too much what definition of 'good results' is used, for this purpose. If there is an existing implementation for one of the approaches you describe, that would be great. Mar 5, 2021 at 21:56