Was ist die maximale Anzahl von stabilen Ehen für eine Instanz des Problems der stabilen Ehe?

Stabiles Eheproblem: http://en.wikipedia.org/wiki/Stable_marriage_problem

Mir ist bekannt, dass für eine SMP-Instanz neben der vom Gale-Shapley-Algorithmus zurückgegebenen viele andere stabile Ehen möglich sind. Wenn wir jedoch nur , die Anzahl der Männer / Frauen, erhalten, stellen wir die folgende Frage: Können wir eine Präferenzliste erstellen, die die maximale Anzahl stabiler Ehen angibt? Was ist die Obergrenze für eine solche Zahl?$n$

Für eine Instanz mit Männern und n Frauen ist die unbedeutende Obergrenze n ! und nichts besseres ist bekannt. Für eine untere Schranke gibt Knuth (1976) eine unendliche Familie von Instanzen mit stabilen Ω ( 2.28 n ) -Anpassungen an, und Thurber (2002) erweitert diese Familie auf alle n .$n$$n$$n!$$\Omega(2.28^n)$$n$

$O(n!/2^n)$$O\left((n!)^\frac{2}{3}\right)$

Das Dokument ist These Nummer 97 auf Seite http://mpla.math.uoa.gr/msc/

Eine exponentielle Obergrenze wurde bei Anna R. Karlin, Shayan Oveis Gharan und Robbie Weber angegeben: Eine einfach exponentielle Obergrenze für die maximale Anzahl stabiler Übereinstimmungen .

$n$$O(2^n)$

Interessante Ergebnisse zu diesem Thema finden Sie auf den Seiten 24 und 25 des Buches: The Stable Marriage Problem von Dan Gusfield und Robert Irving, MIT Press, 1989.