Abstract | ||
---|---|---|
We improve the upper bound for the maximum possible number of stable matchings among <tex>$n$</tex> jobs and <tex>$n$</tex> applicants from 131072<sup>n</sup>+ O(1) to 3.55<sup>n</sup>+ O(1). To establish this bound, we state a novel formulation of a certain entropy bound that is easy to apply and may be of independent interest in counting other combinatorial objects. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/FOCS52979.2021.00029 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Computer science,Upper bound,Entropy | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Cory Palmer | 1 | 0 | 0.34 |
Dömötör Pálvölgyi | 2 | 202 | 29.14 |