¿Cuál es el número máximo de matrimonios estables para una instancia del problema de matrimonio estable?

Problema de matrimonio estable: http://en.wikipedia.org/wiki/Stable_marriage_problem

Soy consciente de que para una instancia de un SMP, son posibles muchos otros matrimonios estables, aparte del que devuelve el algoritmo Gale-Shapley. Sin embargo, si solo se nos da , el número de hombres / mujeres, hacemos la siguiente pregunta: ¿podemos construir una lista de preferencias que proporcione el número máximo de matrimonios estables? ¿Cuál es el límite superior de tal número?$n$

Para una instancia con hombres y n mujeres, el límite superior trivial es n ! , y nada mejor se sabe. Para un límite inferior, Knuth (1976) da una familia infinita de instancias con emparejamientos estables de Ω ( 2.28 n ) , y Thurber (2002) extiende esta familia a todos los n .$n$$n$$n!$$\Omega(2.28^n)$$n$

En mi tesis de maestría se incluye un límite superior en el número máximo de coincidencias estables para una instancia de Matrimonio estable y también se extiende al problema de Compañeros de cuarto estables. El límite es de magnitud y puede ser demostrado que en realidad es de magnitud O ( ( n ! ) $O(n!/2^n)$.$O\left((n!)^\frac{2}{3}\right)$

El documento es el número de tesis 97 en la página http://mpla.math.uoa.gr/msc/

Se ha dado un límite superior exponencial en Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: un límite superior simplemente exponencial en el número máximo de coincidencias estables .

Es bien sabido que una instancia de hombres / mujeres puede tener un número exponencial ( O ( $n$ ) de coincidencias estables, pero todavía está abierto dar un límite superior ajustado. Ver Enciclopedia de algoritmoshttp://www.amazon.com/dp/0387307702$O(2^n)$

Se pueden encontrar resultados interesantes sobre este tema en las páginas 24 y 25 del libro: El problema del matrimonio estable de Dan Gusfield y Robert Irving, MIT Press, 1989.