Stable Roommates Problem: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
n: number of pairs of roommates | $n$: number of pairs of roommates | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 28: | Line 28: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Stable Matching Problem - Stable Roommates Problem - Time.png|1000px]] | [[File:Stable Matching Problem - Stable Roommates Problem - Time.png|1000px]] | ||
Latest revision as of 09:10, 28 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
