Boolean d-Attribute Stable Matching: Difference between revisions
(Created page with "{{DISPLAYTITLE:Boolean d-Attribute Stable Matching (Stable Matching Problem)}} == Description == SMP in the d-attribute model. In the d-attribute model, we assume that there are d different attributes (e.g. income, height, sense of humor, etc.) with a fixed, possibly objective, ranking of the men for each attribute. Each woman’s preference list is based on a linear combination of the attributes of the men, where each woman can have different weights for each attribut...") |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$n$: number of men and number of women | |||
$d$: number of attributes | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 08:23, 10 April 2023
Description
SMP in the d-attribute model. In the d-attribute model, we assume that there are d different attributes (e.g. income, height, sense of humor, etc.) with a fixed, possibly objective, ranking of the men for each attribute. Each woman’s preference list is based on a linear combination of the attributes of the men, where each woman can have different weights for each attribute. Some women may care more about, say, height whereas others care more about sense of humor. Men’s preferences are defined analogously.
Related Problems
Generalizations: Stable Marriage Problem
Related: Almost Stable Marriage Problem, Stable Roommates Problem, Stable Matching Verification, Stable Pair Checking
Parameters
$n$: number of men and number of women
$d$: number of attributes
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Maximum Inner Product Search | assume: OVH then: for an $\epsilon > {0}$ there is a $c$ such that finding a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$. |
2016 | https://arxiv.org/pdf/1510.06452.pdf | link |