Stable Matching Verification (Stable Matching Problem)

From Algorithm Wiki
Jump to navigation Jump to search


Verify that a given matching is stable, given the preferences

Related Problems

Generalizations: Stable Marriage Problem

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


$n$: number of men and number of women

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem Implication Year Citation Reduction
Maximum Inner Product Search assume: OVH
then: for an $\epsilon > {0}$ there is a $c$ such that verifying a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon}).
2016 link