Алгоритм Гейла-Шепли

Алгоритм Гейла-Шепли решает задачу стабильного брака: как сопоставить две группы (например, ординаторов с больницами, студентов со школами) таким образом, чтобы ни одна пара не предпочла друг друга своим назначенным партнерам. Представленный Дэвидом Гейлом и Ллойдом Шепли в 1962 году, алгоритм гарантирует стабильное сопоставление за полиномиальное время посредством процесса отложенного принятия, в котором одна сторона делает предложения последовательно, а другая сторона отвечает, пересматривая выбор по мере появления лучших вариантов.