<p>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 <em>threesome roommates problem</em>, is NP-complete.</p>
<p>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.</p>
<p>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).</p>
<p>An algorithm for a foursome version would also be interesting.</p>

CC BY-SA 4.0
2021-03-05T14:15:07.553Z
What does it mean for a solution to be an approximation?
Chandra Chekuri
CC BY-SA 4.0
2021-03-05T20:56:38.937Z
I mean an algorithm that will probably yield moderately good results, but which isn't mathematically guaranteed to the best.
Raffi
CC BY-SA 4.0
2021-03-05T21:01:37.757Z
Cross-posted: https://cstheory.stackexchange.com/q/48535/5038, https://cs.stackexchange.com/q/136212/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<ds.algorithms><matching>
Is there an approximation algorithm for the three-person stable roommates problem?
Raffi
# Is there an approximation algorithm for the three-person stable roommates problem?

(Asked by: username_0 on 2021-03-05)

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.

**Tags:** ds.algorithms, matching
> **Comments:**
> **username_1**: What does it mean for a solution to be an approximation?  
> **username_0**: I mean an algorithm that will probably yield moderately good results, but which isn't mathematically guaranteed to the best.  
> **username_2**: Cross-posted: https://cstheory.stackexchange.com/q/48535/5038, https://cs.stackexchange.com/q/136212/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 0 answers

