Combinatorial Optimization Reading Group - Madison Van Dyk

Title: Approximation Algorithms for the Stable Marriage Problem

Abstract:

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.