Mertens, S.
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 32) 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 support the conjecture that p(n) = Theta(n(-1/4)).