Stable Pair Checking

Description

Verify that a given pairing 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 Matching Verification

Parameters

$n$: number of pairs of roommates

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 any $\epsilon > {0}$, there is a $c$ such that determining whether a given pair is part of any or all stable matchings in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$	2016	https://arxiv.org/pdf/1510.06452.pdf	link
Maximum Inner Product Search	assume: NSETH then: for any $\epsilon > {0}$ there is a $c$ such that determining whether a gaiven pair is part of any or all stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires co-nondeterministic time $\Omega(n^{2-\epsilon})$	2016	https://arxiv.org/pdf/1510.06452.pdf	link
Maximum Inner Product Search	assume: NSETH then: for any $\epsilon > {0}$ there is a $c$ such that determining whether a gaiven pair is part of any or all stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires nondeterministic time $\Omega(n^{2-\epsilon})$	2016	https://arxiv.org/pdf/1510.06452.pdf	link