This is an old revision of the document!
Table of Contents
Chapter 1 - Introduction: Some Representative Problems
1.1 - A First Problem: Stable Matching
The stable matching problem deals with creating a self-reinforcing selection process. There are two groups, and all the members of each group has a preference profile that lists ranks all members of the other group in order of who that member would like to be matched with. The solution should be self-reinforcing, meaning that members not paired together have no desire to change their matching after the algorithm finishes. The Gale-Shapley algorithm solves the problem as follows for two groups A and B, where all members are initially unmatched:
While there is still a free member in A Choose a member "a" in A Let "b" be highest ranked member of B in "a"'s preference list that a has not already tried to match with If "b" is not already matched with another member of A, then "b" matches with "a" Else if "b" is already matched If "a" is higher on "b"'s preference list than "b"'s current match, then a matches with "b" and "b"'s previous match becomes unmatched Else "a" remains free
In terms of readability I would rank this section a 7/10.
1.2 - Five Representative Problems
We have to be mathematically precise in how we define in order to write and prove an algorithm for it. Graphs can show pairs between two sets of data. The Interval Scheduling Problem attempts to maximize the number of individuals that can use a resource when each individual requests a specific time interval (a starting and stopping time, not simply a length of time). The Weighted Interval Scheduling Problem attaches weights to each individual's interval and the goal is to maximize the value of the schedule when adding up all the weights.