Qual é o número máximo de casamentos estáveis ​​para uma instância do problema do casamento estável?

24

Problema no casamento estável: http://en.wikipedia.org/wiki/Stable_marriage_problem

Estou ciente de que, para uma instância de um SMP, muitos outros casamentos estáveis ​​são possíveis além daquele retornado pelo algoritmo Gale-Shapley. No entanto, se recebermos apenas , o número de homens / mulheres, fazemos a seguinte pergunta - Podemos construir uma lista de preferências que ofereça o número máximo de casamentos estáveis? Qual é o limite superior desse número?n

asc
fonte

Respostas:

24

Para um exemplo com homens e n mulheres, o limite superior trivial é n ! , e nada melhor é conhecido. Para um limite inferior, Knuth (1976) dá uma família infinito de casos com Ω ( 2,28 N ) emparelhamentos estáveis, e Thurber (2002) estende-se esta família de todos os n .nnn!Ω(2.28n)n

Serge Gaspers
fonte
4
Na verdade, eu acredito que esta família de instâncias (por potências de dois) é devido a Irving e Couro e que Knuth provou que a relação de recorrência satisfeito por esta família é Ω(2.28n)
gstat
11
RW Irving e P. Leather. A complexidade de contar casamentos estáveis. Jornal SIAM sobre computação, 15: 655-667,1986
gstat
18

O(n!/2n)O((n!)23)

O documento é a tese número 97 na página http://mpla.math.uoa.gr/msc/

gstat
fonte
4

nO(2n)

Snowie
fonte
2
xn=3xn/222xn/44
1

Resultados interessantes sobre esse assunto podem ser encontrados nas páginas 24 e 25 do livro: The Stable Marriage Problem, de Dan Gusfield e Robert Irving, MIT Press, 1989.

Joseph Malkevitch
fonte