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

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

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

Дальнейшее обобщение задачи HR возникает в случае, когда каждая больница может быть разделена на несколько отделений, каждое из которых имеет свой кадровый потенциал, а резиденты ранжируют отдельные отделения в порядке предпочтения. Этот вариант моделируется задачей распределения студентов по проектам [ ]. Наконец, задача об устойчивых объектах [ ] является недвухсторонним расширением HR, в котором существует единственный набор агентов, каждый из которых имеет собственную емкость (кадровый потенциал) и ранжирует подмножество других в порядке предпочтения.