Stable Marriage Problem

Given $n$ men and $n$ women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.

Parameters

$n$ : number of men and number of women

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


Manlove; Malley	2005	$O(n^2)$	$O(n^2)$
Unsworth; C.; Prosser; P	2005	$O(n^2)$	$O(n^2)$
Gent; I.P.; Irving; R.W.; Manlove; D.F.; Prosser; P.; Smith; B.M.	2001	$O(n^2)$	$O(n^2)$
Gale–Shapley algorithm	1962	$O(n^2)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms