Chapter 1

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.

The text briefly went through the following five problems. I pulled a few notes just to remember what they are.

• Interval Schedulings
  • Resource with over lapping time requests
  • Goal is to maximize number of requests accepted
• Weighted interval scheduling
  • Similar to the above problem but changed the goal.
  • Instead interval is associated with a value maximize the interval values
• Bipartite Matching
  • matching is a set of ordered pairs
  • perfect matching is when no overlapping between pairs
  • create a bipartite graph with nodes
  • similar to stable matching problem, but no weights.
  • max number of matchings
  • perfect matching if # of x nodes = number of y nodes and max matching = n
• Independent Set
  • general problem
  • want to find largest goup you can invite with out offending any one
  • no efficient algorithm exists
• Competitive Facility Location
  • about who wil win when competing for locations, (nodes)
  • A little confused by this one.