Stable Marriage Problem: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 24: | Line 24: | ||
|- | |- | ||
| [[Valentin Polishchuk, and Jukka Suomela (Almost Stable Marriage Problem Stable Matching Problem)|Valentin Polishchuk, and Jukka Suomela]] || 2008 || $O({1})$ || $O({1})$ || 2 + \epsilon || Parallel || [https://arxiv.org/pdf/0812.4893.pdf Time] | |||
|- | |||
| [[Gale–Shapley algorithm (Stable Marriage Problem Stable Matching Problem)|Gale–Shapley algorithm]] || 1962 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || [http://www.eecs.harvard.edu/cs286r/courses/fall09/papers/galeshapley.pdf Time] | | [[Gale–Shapley algorithm (Stable Marriage Problem Stable Matching Problem)|Gale–Shapley algorithm]] || 1962 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || [http://www.eecs.harvard.edu/cs286r/courses/fall09/papers/galeshapley.pdf Time] | ||
|- | |- | ||
| Line 38: | Line 40: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Stable Matching Problem - Stable Marriage Problem - Time.png|1000px]] | [[File:Stable Matching Problem - Stable Marriage Problem - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Stable Matching Problem - Stable Marriage Problem - Space.png|1000px]] | [[File:Stable Matching Problem - Stable Marriage Problem - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Stable Matching Problem - Stable Marriage Problem - Pareto Frontier.png|1000px]] | [[File:Stable Matching Problem - Stable Marriage Problem - Pareto Frontier.png|1000px]] | ||
Revision as of 13:04, 15 February 2023
Description
Given $n$ men and $n$ women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.
Related Problems
Generalizations: Stable Roommates Problem
Subproblem: Almost Stable Marriage Problem, Boolean d-Attribute Stable Matching, Stable Matching Verification, Stable Pair Checking
Related: Boolean d-Attribute Stable Matching, Stable Matching Verification, Stable Pair Checking
Parameters
n: number of men and number of women
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Valentin Polishchuk, and Jukka Suomela | 2008 | $O({1})$ | $O({1})$ | 2 + \epsilon | Parallel | Time |
| Gale–Shapley algorithm | 1962 | $O(n^{2})$ | $O(n)$ | Exact | Deterministic | Time |
| Manlove; Malley | 2005 | $O(n^{2})$ | $O(n^{2})$? | Exact | Deterministic | Time |
| Unsworth; C.; Prosser; P | 2005 | $O(n^{2})$ | $O(n^{2})$? | Exact | Deterministic | Time |
| Gent; I.P.; Irving; R.W.; Manlove; D.F.; Prosser; P.; Smith; B.M. | 2001 | $O(n^{2})$ | $O(n^{2})$? | Exact | Deterministic | Time |
| S. S. TSENG and R. C. T. LEE | 1984 | $O(n^{2})$ | $O(n)$ per processor? | Exact | Parallel | Time |
| [[Tomas Feder, Nimrod Megiddoy, Serge A� Plotki (Stable Marriage Problem Stable Matching Problem)|Tomas Feder, Nimrod Megiddoy, Serge A� Plotki]] | 1994 | $O(n^{0.5})$ | $O(n^{0.5})$ auxiliary per processor? | Exact | Parallel | Time |
Time Complexity Graph
Space Complexity Graph
Pareto Frontier Improvements Graph
