My notes on Chapter 1 readings

This sections talks about the origination of the matching problem and the real-life implications such problem can have. A stable, self-enforcing matching system has to be established in order to have everyone’s self-interest prevent offers from being retracted or redirected. The section then shows an algorithm that produces stable matching and shows a proof of the effectiveness of the algorithm.

The motivation stems from the demand to avoid chaos in any matching problem such as application process of a summer internships, or proposal and acceptance between man and woman, or any process that involves two parties to make choices between the alternatives based on preferences.

How useful is this algorithm in real life? This algorithm assumes the knowledge of all men and women, meaning that all men and women are aware of all their possible options at the time of execution of the algorithm, which is often not the case in real life, where unexpected new parties could enter the show any time. The while-loop may never end.

Readable: 5 Interesting: 7

Interval sheduling Input: Jobs with periods. Output: Maximum subset of compatible jobs.

Weighted Interval sheduling Input: Jobs with periods and weights. Output: Maximum weighted subset of compatible jobs.

Bipartite matching Matchings in bipartite graphs can model situations in which objects are being assigned to other objects. output: maximum matching

Independant set Motivation: The Independent Set Problem encodes any situation in which you are trying to choose from among a collection of objects and there are pairwise conflicts among some of the objects. Interval Scheduling and Bipartite Matching can both be encoded as special cases of the Independent Set Problem.

Readable/Interesting: 5 5