Stable Marriage (13)
Michael L. Littman
October 22nd, 1998
RESIDENCY MATCHING
The Medical Track
Residency is Special
The Match
THE STABLE MARRIAGE PROBLEM
Simplified Problem
Example
Stability
Stability Checking
Rank Computation
THE MATCHING ALGORITHM
Fundamental Result
Matching Algorithm
In Words
More Theorems
Time Analysis
Improving the Running Time
UNDERSTANDING THE ALGORITHM
Termination
Correctness
Boy Optimality
Girl Pessimality
BACK TO THE HOSPITAL
Matching Students to Hospitals
Matching Algorithm
Controversy!
The Study
The Decision
OTHER NEAT FACTS
Next:
RESIDENCY MATCHING
