Title | : | Stability, Popularity, and Lower Quotas |
Speaker | : | Meghana Nasre (IIT Madras) |
Details | : | Thu, Dec 20, 2018 11:00 AM, @ Turing Hall |
Abstract | : | We consider the problem of assigning a set of men to a set of women
where each participant ranks members of the opposite side in an order of preference. This is called the stable marriage problem in literature. It is well known that every instance of the stable marriage problem admits a "stable matching" which can be computed efficiently by the Gale and Shapley algorithm. In this talk we consider three variants of the stable marriage problem where (a) Preference lists can contain ties, (b) Preference lists can be incomplete, (c) Vertices can have lower quotas. For each of these variants a different notion of optimality is applicable; yet we show that, simple extensions of the Gale and Shapley algorithm computes an optimal matching in each of them. The talk is based on three papers -- Z. Kiraly (Algorithmica 2011), T. Kavitha (SICOMP 2014) and Nasre and Nimbhorkar (FSTTCS 2017). |