Combinatorial Optimization Reading Group - Adam Brown

Title: Popularity, Mixed Matchings, and Self-duality

Abstract:

This week we continue our discussion of popular matchings. We extend the notion of popularity to mixed matchings, which can be thought of either as probability distributions over matchings, or convex combinations of matchings. We will investigate the properties of the fractional popular matching polytope and provide a small extended formulation. This extended formulation is self-dual, and we will see how we can take advantage of this to learn about the polytope itself. In particular, the authors were able to show that the fractional popular matching polytope is half integral.