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

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