Almost Stable Marriage Problem (Stable Matching Problem)

From Algorithm Wiki
Jump to navigation Jump to search


The task in the Almost Stable Marriage Problem is to find a matching that minimises the number of unstable edges, but the matching does not have to be a maximum matching.

Related Problems

Generalizations: Stable Marriage Problem

Related: Stable Roommates Problem, Boolean d-Attribute Stable Matching, Stable Matching Verification, Stable Pair Checking


$n$: number of men and number of women

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Valentin Polishchuk, and Jukka Suomela 2008 $O({1})$ $O({1})$ 2 + \epsilon Parallel Time