View source for Boolean d-Attribute Stable Matching

{{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 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 == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Problem !! Implication !! Year !! Citation !! Reduction

|-

| [[Maximum Inner Product Search]] ||  style="text-align:left;" | assume: OVH<br/>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 || [[Reduction from Maximum Inner Product Search to Boolean d-Attribute Stable Matching|link]]
|-
|}