Date of Award
2016
Document Type
Open Access Thesis
Department
Mathematics
Sub-Department
College of Arts and Sciences
First Advisor
Eva Czabarka
Abstract
The well-known Gale-Shapley algorithm is a solution to the stable marriage problem, but always results in the same stable marriage, regardless of how the algorithm is executed. Robert Irving and Paul Leather constructed the rotation poset, whose downward closed sets are in one-to-one correspondence with the set of stable marriage assignments. We discuss how to use the rotation poset to find the k-optimal matching, and prove that a k-optimal matching is the same as a minimum regret matching for high enough k. Finally, Dan Gusfield defines the rotation poset for the stable roommate problem, and uses it to efficiently enumerate all stable roommate assignments.
Rights
© 2016, Joe Hidakatsu
Recommended Citation
Hidakatsu, J.(2016). Structure of the Stable Marriage and Stable Roommate Problems and Applications. (Master's thesis). Retrieved from https://scholarcommons.sc.edu/etd/3756