Title: Approximation Algorithms for the Stable Marriage Problem
|Speaker:||Madison Van Dyk|
|Affiliation:||University of Waterloo|
This week we will discuss stable matching when there are unacceptable pairs and preferences include ties. In this setting one can also consider the Hospitals/Residents problem and the variant where ties are one-sided. These variants are NP-hard so we will focus on the approximation algorithms from Zoltán Király's paper "Better and Simpler Approximation Algorithms for the Stable Marriage Problem". These algorithms are combinatorial with relatively clean proofs.
200 University Avenue West
Waterloo, ON N2L 3G1