Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:deirdre:chapter1 [2014/01/15 02:29] – tobind | courses:cs211:winter2014:journals:deirdre:chapter1 [2014/01/16 15:59] (current) – tobind | ||
|---|---|---|---|
| Line 49: | Line 49: | ||
| If we let //S*// denote the set of pairs {(//m, best(m)) : m ∈ M//}, we can prove that every execution of the G-S algorithm results in the set //S*//. | If we let //S*// denote the set of pairs {(//m, best(m)) : m ∈ M//}, we can prove that every execution of the G-S algorithm results in the set //S*//. | ||
| - | So, for men, the G-S algorithm is ideal (but not ideal for women!). We say that //m// is a valid partner for a woman //w// if there is a stable matching that contains the pair (//m,w//) and that //m// is the //worst valid partner// of //w/ if //m// is a valid partner of //w// and no man whom //w// ranks lower than //m// is a valid partner of hers. So, we can then prove that in teh stable matching //S*//, each woman is paired with her worst valid partner. | + | So, for men, the G-S algorithm is ideal (but not ideal for women!). We say that //m// is a valid partner for a woman //w// if there is a stable matching that contains the pair (//m,w//) and that //m// is the //worst valid partner// of //w/ if //m// is a valid partner of //w// and no man whom //w// ranks lower than //m// is a valid partner of hers. So, we can then prove that in the stable matching //S*//, each woman is paired with her worst valid partner. |
| + | I give this a 10 for level of interest. I think the Stable Matching Problem was very cool and also applicable to real-life situations, such as the residents in the hospitals or students looking for internships. There definitely is a very real need for stable matchings to occur. I also realized that an extension of this is most likely what is used by W& | ||
