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

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.