Stable Roommates Problem: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Stable Roommates Problem (Stable Matching Problem)}} == 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$. == Re...") |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
n: number of pairs of roommates | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Revision as of 12:03, 15 February 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
Error creating thumbnail: Unable to save thumbnail to destination
Space Complexity graph
Error creating thumbnail: Unable to save thumbnail to destination
Pareto Decades graph
Error creating thumbnail: Unable to save thumbnail to destination