Stable Roommates Problem: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| 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]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Stable Matching Problem - Stable Roommates Problem - Space.png|1000px]] | [[File:Stable Matching Problem - Stable Roommates Problem - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Stable Matching Problem - Stable Roommates Problem - Pareto Frontier.png|1000px]] | [[File:Stable Matching Problem - Stable Roommates Problem - Pareto Frontier.png|1000px]] | ||
Revision as of 13:04, 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
Space Complexity Graph
Pareto Frontier Improvements Graph
