0
$\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.

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ What would count as an approximate solution? One which has a small number of blocking triples? $\endgroup$
    – Tassle
    Mar 5, 2021 at 12:23
  • $\begingroup$ 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. $\endgroup$
    – Raffi
    Mar 5, 2021 at 20:57
  • $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/48535/5038, cs.stackexchange.com/q/136212/755. Please do not post the same question on multiple sites. $\endgroup$
    – D.W. ♦
    Mar 5, 2021 at 21:01
  • $\begingroup$ 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. $\endgroup$
    – Tassle
    Mar 5, 2021 at 21:05
  • $\begingroup$ 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. $\endgroup$
    – Raffi
    Mar 5, 2021 at 21:56

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.