COMPSCI 70 Chapter Notes - Chapter 4: Stable Marriage Problem, Disjoint Sets, Royal Institute Of Technology
31 Jan 2018
School
Department
Course
Professor
Document Summary
Stable marriage pairing - a disjoint set of boy-girl pairs. There can be more than 1-2 stable pairings for a stable marriage problem (not just the male or female optimal pairing solution) Not all stable marriage problems have a stable solution/pairing. Any proof that there always exists a stable pairing in the stable marriage problem must use the fact that there are two genders in an essential way. Stable marriage algorithm can only work for hetero pairs. Sma does not depend on the order at which suitors propose (if they get to choose which day they propose to their next choice) Stable marriage algorithm will always produce a female-optimal pairing traditional marriage algorithm (tma) - a stable marriage algorithm where the males propose to the females. Note: to prove that the algorithm works, we must prove the following two properties.
