Задача о больницах и резидентах: различия между версиями

Одно из ключевых расширений HR, имеющее большое практическое значение, возникает в том случае, когда экземпляр задачи может включать в себя набор пар, каждая из которых представляет совместный список предпочтений по парам больниц (например, для того, чтобы члены данной пары могли быть расположены географически близко друг к другу). Расширение HR, в котором могут участвовать пары, обозначается HRC; определение стабильности в HRC является естественным расширением определения стабильности в HR (формальное определение HRC см. в [6, раздел 1.6.6]). Известно, что экземпляр задачи HRC не обязательно может выдавать устойчивое паросочетание (см. [6, раздел 1.6.6] и [14, раздел 5.4.3]). Более того, проблема решения вопроса о том, допускает ли экземпляр HRC устойчивое паросочетание, является NP-полной [13].

HR можно рассматривать как обобщение задачи SM вида «от многих к одному». Дальнейшим обобщением SM является задача нахождения устойчивого паросочетания в модели «от многих к многим», в которой резиденты и больницы могут получать множественные назначения с учетом ограничений на кадровый потенциал. В этом случае резиденты и больницы чаще всего называются работниками и фирмами соответственно. Существуют две основные вариации задачи нахождения устойчивого паросочетания «от многих к многим», в которых либо (1) работники ранжируют приемлемые фирмы в порядке предпочтения и наоборот, либо (2) работники ранжируют приемлемые ''подмножества'' фирм в порядке предпочтения и наоборот. Предыдущие работы, относящиеся к обеим моделям, рассмотрены в [4].

Другие варианты задачи HR возникают в случаях, если списки предпочтений включают связи. Это расширение также очень важно с практической точки зрения, поскольку может быть нереалистично ожидать, что популярная больница расположит большое количество претендентов в строгом порядке, особенно если она не учитывает группы претендентов. Расширение задачи HR, в котором списки предпочтений могут включать связи, обозначается HRT. В этом контексте возникают три естественных определения устойчивости, так называемые слабая устойчивость, сильная устойчивость и сверхустойчивость (формальные определения этих понятий см. в [8]). Известно, что слабоустойчивые паросочетания в экземпляре <math>I</math> задачи HRT могут иметь различные размеры, и проблема нахождения слабоустойчивого паросочетания максимальной мощности является NP-полной (подробнее об этом см. Устойчивое бракосочетание со связями и неполными списками). С другой стороны, в отличие от случая слабой устойчивости, сверхустойчивое паросочетание не обязательно должно существовать в I, хотя существует алгоритм с временем выполнения O(L) для поиска такого паросочетания в случае, если таковое существует. Аналогичные результаты имеют место и в случае сильной устойчивости – в этом случае алгоритм с временем выполнения <math>O(L^2)</math> [8] был улучшен алгоритмом с временем выполнения O(CL) [10] и распространен на случай «от многих к многим» [11]. Кроме того, аналоги теоремы о сельских больницах справедливы для HRT при каждом из критериев сверхустойчивости и сильной устойчивости [7, 15].