Stable Roommates Problem

Given $2n$ participants, each of participant ranks the others in strict order of preference. A matching is a set of $n$ disjoint pairs of participants. A matching $M$ in an instance of SRP is stable if there are no two participants $x$ and $y$ , each of whom prefers the other to their partner in $M$ . Such a pair is said to block $M$ , or to be a blocking pair with respect to $M$ .

Parameters

$n$ : number of pairs of roommates

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

				See more
Patrick Posser	2014	$O(n^3)$	$O(n)$
Irving's Algorithm	1985	$O(n^2)$	$O(n^2)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms