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

24

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$

— asc
źródło

24

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$

— Serge Gaspers
źródło

4

Właściwie uważam, że ta rodzina instancji (dla potęg dwóch) jest spowodowana przez Irvinga i Leather, a Knuth udowodnił, że relacja powtarzalności spełniona przez tę rodzinę to

Ω ({2.28}^{n})

$\Omega(2.28^n)$

— gstat

1

RW Irving i P. Leather. Złożoność liczenia stabilnych małżeństw. SIAM Journal on Computing, 15: 655-667,1986

— gstat

18

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!/2^n)$ . $O\left((n!)^\frac{2}{3}\right)$

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

— gstat
źródło

7

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ń .

— domotorp
źródło

4

Dobrze wiadomo, że wystąpienie mężczyzn / kobiet może mieć wykładniczą liczbę ( ) 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)$

— Snowie
źródło

2

x_{n} = 3 x_{n / 2}^{2} - 2 x_{n / 4}^{4}

$x_n = 3x^2_{n/2} - 2x^4_{n/4}$

1

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.

— Joseph Malkevitch
źródło