Vi studerar varianten av det välkända problemet med stabila rumskamrater där deltagarna tillåts uttrycka band i sina preferenslistor. I detta sammanhang är mer än en definition av stabilitet möjlig. Här överväger vi två av dessa stabilitetskriterier, så kallad superstabilitet och svag stabilitet. Vi presenterar en linjär tid algoritm för att hitta en super-stabil matchning om man finns, med tanke på en stabil Roommates instans med kopplingar. Detta står i kontrast till den kända NP-hårdheten hos det analoga problemet under svag stabilitet. Vi utökar också vår algoritm för att klara av preferenslistor som är ofullständiga och/eller delvis beställda. Å andra sidan, för en given Stable Roommates exempel med band och ofullständiga listor, visar vi att de svagt stabila matchningar kan vara av olika storlekar, och problemet med att hitta en maximal kardinalitet svagt stabil matchning är NP-hård, även om ungefärlig inom en faktor på 2.
Irving och Manlove REF presenterade en line-time algoritm för att hitta en superstabil matchning om man finns, med tanke på en stabil rumskamrat instans med band.
The stable roommates problem with ties
{'venue': 'J. Algorithms', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}