Stable husbands
| dc.creator | Knuth, Donald E. | |
| dc.creator | Motwani, Rajeev | |
| dc.creator | Pittel, Boris | |
| dc.date | 1990-01-01 | |
| dc.date.accessioned | 2026-07-07T09:14:44Z | |
| dc.date.available | 2026-07-07T09:14:44Z | |
| dc.description | Suppose $n$ boys and $n$ girls rank each other at random. We show that any particular girl has at least $({1\over 2}-ε) \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 \to \infty$, if $ε$ is any positive constant. The proof emphasizes general methods that appear to be useful for the analysis of many other combinatorial algorithms. | |
| dc.identifier | https://arxiv.org/abs/math/9201303 | |
| dc.identifier | http://arxiv.org/abs/math/9201303 | |
| dc.identifier | Random Structures Algorithms 1 (1990), no. 1, 1--14 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/152782 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.title | Stable husbands | |
| dc.type | text |