Abstrakt. Ett exempel på det klassiska problemet med stabila rumskamrater (sr) behöver inte medge en stabil matchning. Detta motiverar problemet med att hitta en matchning som är "så stabil som möjligt", dvs. medger det minsta antalet blockerande par. I detta papper bevisar vi att, med tanke på en sr instans med n agenter, där alla preferenslistor är fullständiga, problemet med att hitta en matchning med det minsta antalet blockerande par är NP-hård och inte ungefärlig inom n 1 2 −ε, för alla ε > 0, om inte P=NP. Om preferenslistorna innehåller band, förbättrar vi detta resultat till n 1−ε. Dessutom visar vi att, med tanke på ett heltal K och en sr instans I där alla preferenslistor är kompletta, problemet med att avgöra om jag erkänner en matchning med exakt K blockerande par är NP-komplett. Däremot, om K är konstant, ger vi en polynom-tid algoritm som hittar en matchning med högst (eller exakt) K blockerande par, eller rapporterar att ingen sådan matchning finns. Slutligen ger vi övre och nedre gränser för det minsta antalet blockerande par över alla matchningar när det gäller vissa egenskaper hos en stabil partition, med tanke på en sr instans I.
Problemet med att hitta en matchning med det minsta antalet blockerande par är NP-hård, och det är svårt att uppskatta REF.
Almost stable” matchings in the roommates problem
{'venue': 'In Approximation and online algorithms', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}