You are here

A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings

Anna Karlin, University of Washington
Wednesday, October 31, 2018 - 4:10pm
PDL C-401
Anna photo
Stable matching is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley. In this talk, we will describe an improved upper bound on f(n), the maximum number of stable matchings that a stable matching instance of size n can have.
Joint work with Shayan Oveis Gharan and Robbie Weber
*Note: There will be no pre-seminar, only the main talk at 4:10pm.
Event Type: