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

Authors

Arthur T. Benjamin, Harvey Mudd CollegeFollow
Cherlyn Converse, California State University - Fullerton
Henry A. Krieger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

5-1995

Abstract

A stable marriage problem of size 2n is constructed which contains Θ(2ⁿ√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.

DOI

10.1016/0166-218X(95)80006-P

Recommended Citation

Benjamin, A.T., Converse, C., & Krieger, H.A. (1995). How do I marry thee? Let me count the ways! Discrete Applied Mathematics, 59(3): 285-292. DOI: 10.1016/0166-218X(95)80006-P