Каково максимальное количество стабильных браков для случая проблемы стабильного брака?

24

Проблема стабильного брака: http://en.wikipedia.org/wiki/Stable_marriage_problem

Мне известно, что для случая SMP возможны многие другие стабильные браки, кроме одного, возвращенного алгоритмом Гейла-Шепли. Однако, если нам дается только , число мужчин / женщин, мы задаем следующий вопрос: можем ли мы составить список предпочтений, который дает максимальное количество стабильных браков? Какова верхняя граница для такого числа?n

по возрастанию
источник

Ответы:

24

Для случая с мужчинами и женщинами тривиальная верхняя граница равнаи ничего лучше не известно. Для нижней границы Кнут (1976) дает бесконечное семейство примеров со стабильными соответствиями , а Тербер (2002) расширяет это семейство на все .н н н !nnn!Ω(2.28n)n

Серж Гасперс
источник
4
На самом деле, я считаю, что это семейство экземпляров (для степеней двух) связано с Ирвингом и Кожаным, и что Кнут доказал, что рекуррентное соотношение, удовлетворяемое этим семейством, являетсяΩ(2.28n)
gstat
1
Р. У. Ирвинг и П. Кожа. Сложность подсчета стабильных браков. SIAM журнал по вычислениям, 15: 655-667,1986
GSTAT
18

Верхняя граница для максимального количества стабильных совпадений для экземпляра «Стабильный брак» дана в моей магистерской диссертации и распространяется также на проблему «Стабильные соседи по комнате». Эта граница имеет величину и может показать, что на самом деле он имеет величину .O ( ( n ! ) 2O(n!/2n)O((n!)23)

Документ тезис № 97 на странице http://mpla.math.uoa.gr/msc/

GSTAT
источник
4

Хорошо известно, что экземпляр мужчин / женщин может иметь экспоненциальное число ( ) стабильных совпадений, но задание жесткой верхней границы все еще открыто. См. Энциклопедию алгоритмов http://www.amazon.com/dp/0387307702.O ( 2 n )nO(2n)

Snowie
источник
2
Предложение вводит в заблуждение, но я думаю, что оно претендует только на экспоненциальную нижнюю границу: одна из открытых проблем, поставленных Кнутом в его ранней монографии о стабильном браке [11], заключалась в определении максимально возможного числа xn стабильных сопоставлений для любого экземпляра SM с участием n мужчин и n женщин. Эта проблема остается открытой, хотя сам Кнут показал, что xn растет экспоненциально с n. Ирвинг и Кожа [8] предполагают, что, когда n - степень 2, эта функция удовлетворяет рекуррентностиxn=3xn/222xn/44
domotorp
1

Интересные результаты по этому вопросу можно найти на страницах 24 и 25 книги Дана Гусфилда и Роберта Ирвинга «Устойчивый брак», издательство MIT Press, 1989.

Иосиф Малкевич
источник