Jaka jest maksymalna liczba trwałych małżeństw w przypadku problemu stabilnego małżeństwa?

Problem stabilnego małżeństwa: http://en.wikipedia.org/wiki/Stable_marriage_problem

Zdaję sobie sprawę, że w przypadku SMP możliwe jest wiele innych stabilnych małżeństw, z wyjątkiem algorytmu Gale-Shapleya. Jeśli jednak otrzymamy tylko , liczbę mężczyzn / kobiet, zadajemy następujące pytanie: Czy możemy stworzyć listę preferencji, która daje maksymalną liczbę trwałych małżeństw? Jaka jest górna granica takiej liczby?$n$

Na przykład dla mężczyzn i kobiet, trywialna górna granica toi nic lepszego nie jest znane. Dla dolnej granicy Knuth (1976) podaje nieskończoną rodzinę instancji ze stabilnymi dopasowaniami , a Thurber (2002) rozszerza tę rodzinę na wszystkie .$n$$n$$n!$$\Omega(2.28^n)$$n$

Górna granica maksymalnej liczby stabilnych dopasowań dla instancji Stabilnego Małżeństwa jest podana w mojej pracy magisterskiej i obejmuje również problem Stabilnych Współlokatorów. Granica ma wielkość i może być pokazał, że faktycznie ma wielkość O ( ( n ! ) $O(n!/2^n)$.$O\left((n!)^\frac{2}{3}\right)$

Dokument jest numerem pracy 97 na stronie http://mpla.math.uoa.gr/msc/

Wykładnicza górna granica została podana w Annie R. Karlin, Shayan Oveis Gharan, Robbie Weber: Prosta wykładnicza górna granica maksymalnej liczby stabilnych dopasowań .

Dobrze wiadomo, że wystąpienie mężczyzn / kobiet może mieć wykładniczą liczbę ( O ( 2 n ) ) stabilnych dopasowań, ale podanie ciasnej górnej granicy jest nadal otwarte. Zobacz Encyklopedia algorytmów http://www.amazon.com/dp/0387307702$n$$O(2^n)$

Ciekawe wyniki na ten temat można znaleźć na stronach 24 i 25 książki: The Stable Marriage Problem autorstwa Dana Gusfielda i Roberta Irvinga, MIT Press, 1989.