Name
Abstract | ||
|---|---|---|
We introduce a restriction of the stable roommates problem in which roommate pairs are ranked globally. In contrast to the unrestricted problem, weakly stable matchings are guaranteed to exist, and additionally, can be found in polynomial time. However, it is still the case that strongly stable matchings may not exist, and so we consider the complexity of finding weakly stable matchings with various desirable properties. In particular, we present a polynomial-time algorithm to find a rank-maximal (weakly stable) matching. This is the first generalization of the algorithm due to Irving et al. [18] to a non-bipartite setting. Also, we prove several hardness results in an even more restricted setting for each of the problems of finding weakly stable matchings that are of maximum size, are egalitarian, have minimum regret, and admit the minimum number of weakly blocking pairs. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-77105-0_48 | workshop on internet and network economics |
Keywords | DocType | Volume |
globally-ranked pair,restricted setting,stable roommates problem,minimum number,weakly stable,unrestricted problem,polynomial-time algorithm,weakly stable matchings,non-bipartite setting,stable matchings,minimum regret,polynomial time,stable matching | Conference | 5 |
Issue | ISSN | ISBN |
4 | 0302-9743 | 3-540-77104-2 |
Citations | PageRank | References |
14 | 0.78 | 25 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Abraham | 1 | 190 | 15.88 |
| Ariel Levavi | 2 | 25 | 2.50 |
| David F. Manlove | 3 | 761 | 60.45 |
| Gregg O'Malley | 4 | 73 | 4.39 |