Vi studerar en version av de välkända sjukhus / invånare problem där deltagarnas preferenser kan innebära band eller andra former av likgiltighet. I detta sammanhang undersöker vi begreppet stark stabilitet och hävdar att detta kan vara den lämpligaste och mest önskvärda formen av stabilitet i många praktiska situationer. När likgiltigheten är i form av band, beskriver vi en O(a 2 ) algoritm för att hitta en starkt stabil matchning, om man finns, där a är antalet ömsesidigt godtagbara (bosatt, sjukhus) par. Vi ger också en lägre gräns i detta fall i termer av komplexiteten i att avgöra om en bipartit graf innehåller en perfekt matchning. Däremot bevisar vi att det blir NP-komplett att avgöra om en starkt stabil matchning existerar om preferenserna tillåts vara godtyckliga partiella order.
I synnerhet, under stark stabilitet, stabila matchningar kanske inte alltid finns och det visas i REF att problemet med att avgöra om en starkt stabil matchning finns, med tanke på ett exempel på stabila äktenskapsproblem med delvis beställda preferenser, är NP-fullständig.
Strong stability in the hospitals/residents problem
{'venue': 'In Proceedings of STACS 2003: the 20th Annual Symposium on Theoretical Aspects of Computer Science', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}