Berapa jumlah maksimum pernikahan stabil untuk contoh Masalah Pernikahan yang Stabil?

Masalah Pernikahan yang Stabil: http://en.wikipedia.org/wiki/Stable_marriage_problem

Saya sadar bahwa untuk instance SMP, banyak pernikahan stabil lainnya dimungkinkan selain dari yang dikembalikan oleh algoritma Gale-Shapley. Namun, jika kita hanya diberikan , jumlah pria / wanita, kita mengajukan pertanyaan berikut - Bisakah kita membuat daftar preferensi yang memberikan jumlah maksimum pernikahan stabil? Apa batas atas angka seperti itu?$n$

Untuk sebuah contoh dengan laki-laki dan perempuan, sepele atas terikat adalah, dan tidak ada yang lebih baik yang diketahui. Untuk batas bawah, Knuth (1976) memberikan keluarga tak terbatas contoh dengan pertandingan stabil, dan Thurber (2002) memperluas keluarga ini ke semua .$n$$n$$n!$$\Omega(2.28^n)$$n$

Batas atas pada jumlah maksimum pencocokan stabil untuk contoh Pernikahan Stabil diberikan dalam tesis Master saya dan diperluas ke masalah Teman Sekamar Stabil juga. Batasnya besarnya dan dapat diperlihatkan bahwa itu sebenarnya besarnya O ( ( n ! ) $O(n!/2^n)$.$O\left((n!)^\frac{2}{3}\right)$

Dokumen ini adalah tesis nomor 97 di halaman http://mpla.math.uoa.gr/msc/

Batas atas eksponensial telah diberikan dalam Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Upper Eksponensial Upper Bound pada Jumlah Maksimum dari Pencocokan Stabil .

Diketahui bahwa turunan dari pria / wanita dapat memiliki angka eksponensial ( O ( 2 n ) ) dari pasangan stabil, tetapi memberikan batas atas yang ketat masih terbuka. Lihat Ensiklopedia algoritma http://www.amazon.com/dp/0387307702$n$$O(2^n)$

Hasil menarik tentang masalah ini dapat ditemukan di halaman 24 dan 25 buku: The Stable Marriage Problem oleh Dan Gusfield dan Robert Irving, MIT Press, 1989.