Stable husbands
Stable husbands
复制标题
稳定的丈夫
DOI：
10.1002/rsa.3240010102
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
B. Pittel
中科院分区：
文献类型：
--
作者：
D. Knuth;R. Motwani;B. Pittel
.假设n个男孩和n个女孩随机排列。我们证明，在由这些排序定义的所有盖尔/沙普利稳定匹配的集合中，任何特定的女孩至少有（12 − 1）ln n个不同的丈夫，最多有（1 + 1）ln n个不同的丈夫，当n → ∞时，概率接近1，如果n是任何正的常数。证明强调的一般方法，似乎是有用的许多其他组合算法的分析。
. Suppose n boys and n girls rank each other at random. We show that any particular girl has at least ( 12 − ǫ ) ln n and at most (1 + ǫ ) ln n different husbands in the set of all Gale/Shapley stable matchings defined by these rankings, with probability approaching 1 as n → ∞ , if ǫ is any positive constant. The proof emphasizes general methods that appear to be useful for the analysis of many other combinatorial algorithms.