Den klassiska Stable Roommates problemet frågar om det är möjligt att ha en matchning av ett jämnt antal agenter så att inga två agenter som inte matchas med varandra skulle föredra att vara med varandra snarare än med sina tilldelade partners. Vi undersöker stabila rumskamrater med fullständiga (dvs varje agent kan matchas med någon annan agent) eller ofullständiga preferenser, med band (dvs två agenter anses vara av samma värde som någon agent) eller utan band. Det är känt att i allmänhet tillåter band gör problemet NP-fullbordande. Vi tillhandahåller algoritmer för stabila rumskamrater som, jämfört med dem i litteraturen, är effektivare när inmatningspreferenserna är fullständiga och har viss strukturell egendom, såsom att vara narcissistisk, ental, och singel-crossing. Men när preferenserna är ofullständiga och har band, visar vi att vara singel-talad och singel-crossing inte minskar den beräknings komplexitet-Stable Roommates fortfarande NP-fullständig.
Bredereck m.fl. REF presenterade polynom-tidsalgoritmer för stabila rumskamrat problem med komplett narcissistiska, enkel-talade och singel-crossing preferenser.
Stable Roommates with Narcissistic, Single-Peaked, and Single-Crossing Preferences
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}