Stable Roommates Problem with Random Preferences

Abstract

The stable roommates problem with $n$ agents has worst case complexity $O(n^2)$ in time and space. Random instances can be solved faster and with less memory, however. We introduce an algorithm that has average time and space complexity $O(n^{\frac{3}{2}})$ for random instances. We use this algorithm to simulate large instances of the stable roommates problem and to measure the probabilty $p_n$ that a random instance of size $n$ admits a stable matching. Our data supports the conjecture that $p_n=\Theta (n^{-1/4})$.

14 pages, 6 figures, 4 algorithms, 1 table; Journal of Statistical Mechanics: Theory and Experiment (2015) P01020

References in corpus (1)

• Random Stable Matchings

Cited by in corpus (1)

• Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem