Papers for

matching algorithm developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Improved upper bound on number of stable matchings in pairing problems

A Sub-$3^n$ Upper Bound on the Number of Stable Matchings

Abstract: We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a new $2.999^n$ upper bound on the number of stable matchings with $n$ men and $n$ women. This improves the best-known previous result by Palmer and Pálvölgyi. This result gets much closer to the well-known lower bound $\frac{2.28^n}{\text{poly}(n)}$. We refine their entropy-based framework by capturing broader structural relationships among stable matchings. To capture these relationships, we introduce new frameworks, including cones and supports. This establishes the $3.332^n$ bound. We also exploit relationships among local structures and use a charging argument to improve the bound to $2.999^n$.

Wed 4 NovData Structures and AlgorithmsDiscrete Mathematics
The gist
Counting how many stable ways to match pairs of men and women can be tricky and has interested researchers for decades. The authors found a better way to limit the maximum number of these stable matchings, showing it is less than three times itself for each person involved. They built on earlier math methods by including more detailed relationships and introduced new tools to understand these matchings. This brings the upper estimate closer to the lowest known estimates, narrowing the possible range.
Open → 2611.06604v1