Combinatorial Optimization Reading Group - Matthew Louis Gerstbrein

Title: Stable marraige with general preferences

Abstract:

This week, we discuss a generalization of the standard stable marriage problem, in which one side has a complete, totally ordered, strict preference list while the other has preferences given in terms of arbitrary binary relations. These binary relations need not be transitive or acyclic. We will discuss this generalization (known as SMG) as it relates to another variant of stable matching in which ties and incomplete lists are allowed, allowing us to deduce complexity results for this new variant SMG. Additionally, we will discuss algorithmic results and a related linear programming formulation.