Name
Abstract | ||
|---|---|---|
Stable matching is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley. In this paper, we provide a new upper bound on f(n), the maximum number of stable matchings that a stable matching instance with n men and n women can have. It has been a long-standing open problem to understand the asymptotic behavior of f(n) as n→∞, first posed by Donald Knuth in the 1970s. Until now the best lower bound was approximately 2.28n, and the best upper bound was 2nlogn− O(n). In this paper, we show that for all n, f(n) ≤ cn for some universal constant c. This matches the lower bound up to the base of the exponent. Our proof is based on a reduction to counting the number of downsets of a family of posets that we call “mixing”. The latter might be of independent interest.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3188745.3188848 | STOC '18: Symposium on Theory of Computing
Los Angeles
CA
USA
June, 2018 |
Keywords | DocType | Volume |
stable matching,stable marriage problem,counting,downset,poset | Conference | abs/1711.01032 |
ISSN | ISBN | Citations |
0737-8017 | 978-1-4503-5559-9 | 1 |
PageRank | References | Authors |
0.35 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anna R. Karlin | 1 | 4429 | 646.72 |
| Shayan Oveis Gharan | 2 | 323 | 26.63 |
| Robbie Weber | 3 | 2 | 0.71 |