This is an old revision of the document!
Chapter 1
1.1: Stable Matching Problem I read the chapter before we worked on this problem in class and it made everything so simple and easy to understand. I am also in the middle of sorority recruitment and so it seemed very relevant. Since as a member of a sorority we have preferences and the freshman have preferences and this whole week is based on matching the sorority with a pledge class. What is actually really interesting about recruitment that most people don't know is that a computer algorithm is used to do the matching every night. (Pretty crazy).
The text goes over an example with marriages, which we also used in class. The Gale-Sharpley algorithm to solve it is very simple and seeing it in code made it clear why it worked so well. I was surprised to find that it had a unique stable solution and that the women and men experience the opposite preference changes through out the algorithm. Women move to better matches, while men move to worse.
I found the proofs most interesting because they were succint and simple. I am also a sucker for a proof by contradiction. I think the best proof was showing it was a stable matching since once you know the trick to show the contradiction it is only a couple lines. I would like to go over the proof that the solution is unique in class since that is the most complicated.
1.2 Five Representative Problems
- Interval Schedulings
- Weighted interval scheduling
- Bipartite Matching
- Independent Set
- Competitive Facility Location
