Title: Stable Matchings and a Matroid Generalization
| Speaker: | Jacob Skitsko |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: Today we'll continue our theme of matchings and talk about stable matchings! We won't assume much previous experience with stable matchings, and we will (re)introduce what they are. After, we will talk about classic results and some more recent approximations for generalizations of the problem. In the classic stable matching problem, we are given a bipartite graph and for each vertex we are given a list of strict preferences over other vertices. The goal is to find a "stable" matching, where no two vertices would prefer being matched to other vertices. This can be accomplished using the classic Gale-Shapley algorithm, which we will review. We will also consider when ties and indifferences can be present in the list of preferences. With such preferences, the problem becomes APX-Hard. However, McDermid showed it is possible to achieve a 1.5 approximation. We will talk about this, and comment on a recent generalization to matroids from Csaji, Kiraly, and Yokoi.