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

Практические приложения задачи HR широко распространены. В первую очередь они возникают в контексте централизованных автоматизированных схем подбора кандидатов на должности (например, студентов-медиков в больницы, выпускников школ в университеты, учеников начальных школ в средние школы). Возможно, самым известным примером такой схемы является Национальная программа подбора резидентов (National Resident Matching Program, NRMP) в США [16], которая ежегодно распределяет около 31 000 студентов-медиков (называемых резидентами) на их первые должности в больницах, учитывая предпочтения резидентов по отношению к больницам и наоборот, а также кадровый потенциал больниц. Аналоги программы NRMP существуют и в других странах, включая Канаду [17], Шотландию [18] и Японию [19]. Эти схемы подбора в основном используют расширения алгоритма RGS для задачи HR.

Другие варианты задачи 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].

Было сформулировано несколько аппроксимационных алгоритмов поиска слабоустойчивого паросочетания максимальной мощности для экземпляра HRT, в котором каждая больница имеет кадровый потенциал 1 (подробнее об этом см. [[Устойчивое бракосочетание со связями и неполными списками]]). Остается открытым вопрос о расширении этих алгоритмов или о формулировании эффективных эвристик для случая HRT с произвольными значениями кадрового потенциала. Эта задача особенно актуальна с практической точки зрения, поскольку, как уже отмечалось в разделе «Применение», больницы могут захотеть включить связи в свои списки предпочтений. В этом случае слабая устойчивость является наиболее часто используемым критерием устойчивости, поскольку существование такого паросочетания гарантируется. Попытка обеспечить совпадение для как можно большего числа резидентов мотивирует на поиск больших слабоустойчивых паросочетаний.

*[[Оптимальное устойчивое бракосочетание]]

*[[Устойчивое бракосочетание]]

*[[Устойчивое бракосочетание и дискретный выпуклый анализ]]

*[[Устойчивое бракосочетание со связями и неполными списками]]