Stable Roommates Problem: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
n: number of pairs of roommates | $n$: number of pairs of roommates | ||
== Table of Algorithms == | == Table of Algorithms == | ||
Revision as of 08:23, 10 April 2023
Description
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$.
Related Problems
Subproblem: Stable Marriage Problem
Related: Almost Stable Marriage Problem, Boolean d-Attribute Stable Matching, Stable Matching Verification, Stable Pair Checking
Parameters
$n$: number of pairs of roommates
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Irving's Algorithm | 1985 | $O(n^{2})$ | $O(n^{2})$? | Exact | Deterministic | Time |
| Patrick Posser | 2014 | $O(n^{3})$ | $O(n)$ | Exact | Deterministic | Time & Space |
Time Complexity Graph
Space Complexity Graph
Time-Space Tradeoff
