Name
Abstract | ||
|---|---|---|
We consider the stable matching problem when the preference lists are not given explicitly but are represented in a succinct way and ask whether the problem becomes computationally easier. We give subquadratic algorithms for finding a stable matching in special cases of two very natural succinct representations of the problem, the d-attribute and d-list models. We also give algorithms for verifying a stable matching in the same models. We further show that for $$d = \\omega \\log n$$ both finding and verifying a stable matching in the d-attribute model requires quadratic time assuming the Strong Exponential Time Hypothesis. The d-attribute model is therefore as hard as the general case for large enough values of d. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-34171-2_21 | CSR |
Keywords | Field | DocType |
Stable matching, Attribute model, Subquadratic algorithms, Conditional lower bounds, SETH | Stable roommates problem,Discrete mathematics,Combinatorics,Stable marriage problem,Ask price,Single peaked preferences,Computer science,Algorithm,Time complexity,Exponential time hypothesis | Journal |
Volume | ISSN | Citations |
abs/1510.06452 | 0302-9743 | 6 |
PageRank | References | Authors |
0.43 | 23 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Moeller | 1 | 6 | 0.77 |
| Ramamohan Paturi | 2 | 1260 | 92.20 |
| Stefan Schneider | 3 | 56 | 3.07 |