Hospitals/Residents (auch College Admissions Problem) verallgemeinert das Stable-Marriage-Problem um Kapazitäten: Bewerber (Residents) haben Präferenzlisten über Krankenhäuser, und jedes Krankenhaus kann mehrere Plätze vergeben, hat aber eine Kapazität. Gesucht ist eine stabile Zuordnung — es darf kein Bewerber-Krankenhaus-Paar geben, das einander gegenüber der aktuellen Zuweisung vorzieht.
Das Modell
Formal liegt ein bipartiter Graph vor: Auf der einen Seite die Bewerber (Knoten mit Präferenzliste), auf der anderen die Krankenhäuser mit Präferenzliste und Kapazität (Anzahl verfügbarer Plätze). Eine Zuordnung weist jedem Bewerber höchstens ein Krankenhaus zu und jedem Krankenhaus höchstens so viele Bewerber, wie seine Kapazität erlaubt. Stable Marriage ist der Spezialfall, in dem jede Krankenhaus-Kapazität genau 1 beträgt.
Algorithmus und Eigenschaften
Die bewerberorientierte Variante des Gale-Shapley-Algorithmus (Deferred Acceptance) findet immer eine stabile Zuordnung: Bewerber schlagen der Reihe nach vor, Krankenhäuser behalten vorläufig die besten Kandidaten bis zur Kapazitätsgrenze und lehnen schlechtere ab. Läuft der Algorithmus bewerberorientiert, ist das Ergebnis bewerber-optimal (jeder Bewerber bekommt sein bestmögliches stabile Ergebnis); läuft er krankenhausorientiert, entsprechend krankenhaus-optimal. Die Laufzeit beträgt O(n·m) bei n Bewerbern und m Plätzen. Stabilität bleibt eine eigene Anforderung: Eine Zuordnung mit maximaler Gesamtzufriedenheit oder ein gewichtetes Matching ist nicht automatisch stabil.
Praxis
Das bekannteste Beispiel ist das National Resident Matching Program (NRMP) in den USA, das seit 1952 Medizinstudierende auf Facharztstellen verteilt. Gleiche Mechanismen steuern Schulplatzvergabe (etwa in Boston und New York), Studienplatzvergabe und Wohnungszuteilungen. Das Verfahren ist eng verwandt mit dem b-Matching (dort sind Kapazitäten Teil der Kantenauswahl) und dem Stable-Roommates-Problem (dort fehlt die Zweiteilung der Gruppen).