How Do I Marry Thee? Let Me Count the Ways!

Document Type



Mathematics (HMC)

Publication Date



A stable marriage problem of size 2n is constructed which contains Θ(2n√n) stable matchings. This construction provides a new lower bound on the maximum number of stable matchings for problems of even size and is comparable to a known lower bound when the size is a power of 2. The method of construction makes use of special properties of the latin marriage problem, which we develop.

Rights Information

© 1995 Elsevier Science B.V.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.