Math
Устойчивые паросочетания
Наблюдайте алгоритм Гейла—Шепли: предложения, временные пары и отказы. Меняйте предлагающую сторону и проверяйте отсутствие блокирующих пар в конце.
Что попробовать
Пройдите предложения и отказы алгоритма Гейла—Шепли. У сторон строгие случайные предпочтения. Смените предлагающую сторону для сравнения; у готового соответствия нет блокирующей пары.
Уравнения модуля
Уравнения Свободный предлагающий обращается к самому предпочтительному из получателей, которым он ещё не предлагал Получатель оставляет себе более предпочтительное предложение и отклоняет другое Не более n² предложений; полные строгие списки дают устойчивое паросочетание Оптимально для предлагающих среди устойчивых паросочетаний
