Combinatorial Optimization Reading Group - Madison Van Dyk

Friday, June 28, 2019 1:00 pm - 1:00 pm EDT (GMT -04:00)

Title: Approximation Algorithms for the Stable Marriage Problem

Speaker: Madison Van Dyk
Affiliation: University of Waterloo
Room: MC 5479

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.