Проблема стабильного брака: http://en.wikipedia.org/wiki/Stable_marriage_problem
Мне известно, что для случая SMP возможны многие другие стабильные браки, кроме одного, возвращенного алгоритмом Гейла-Шепли. Однако, если нам дается только , число мужчин / женщин, мы задаем следующий вопрос: можем ли мы составить список предпочтений, который дает максимальное количество стабильных браков? Какова верхняя граница для такого числа?
ds.algorithms
co.combinatorics
graph-algorithms
heuristics
matching
по возрастанию
источник
источник
Верхняя граница для максимального количества стабильных совпадений для экземпляра «Стабильный брак» дана в моей магистерской диссертации и распространяется также на проблему «Стабильные соседи по комнате». Эта граница имеет величину и может показать, что на самом деле он имеет величину .O ( ( n ! ) 2O(n!/2n) O((n!)23)
Документ тезис № 97 на странице http://mpla.math.uoa.gr/msc/
источник
Экспоненциальная верхняя граница была дана у Анны Р. Карлин, Шаян Овейс Гаран, Робби Вебера: просто экспоненциальная верхняя граница для максимального количества стабильных совпадений .
источник
Хорошо известно, что экземпляр мужчин / женщин может иметь экспоненциальное число ( ) стабильных совпадений, но задание жесткой верхней границы все еще открыто. См. Энциклопедию алгоритмов http://www.amazon.com/dp/0387307702.O ( 2 n )n O(2n)
источник
Интересные результаты по этому вопросу можно найти на страницах 24 и 25 книги Дана Гусфилда и Роберта Ирвинга «Устойчивый брак», издательство MIT Press, 1989.
источник