Combinatorial Optimization Reading Group - Ishan Bansal

Title: Maximum Cardinality Popular Matchings

Abstract:

We have seen the algorithm by Abraham, Irving, Kavitha, and Mehlhorn which deals with finding popular matchings (can be easily modified to give maximum cardinality popular matchings) in bipartite graphs with one-sided preference lists. This week we shall find maximum cardinality popular matchings in bipartite graphs with two-sided preference lists. This is based on the work of Huang and Kavitha who give nice structural results related to popular matchings along with an algorithm to find a maximum cardinality popular matching. We will not assume any results from previous talks.