Random Stable Roommates instances are typically nearly solvable: they have few odd cycles that block stability, and the stable matchings or partitions they admit are usually few, which makes many NP-hard optimization problems easy in practice.
Computational Complexity of Stable Marriage and Stable Roommates and Their Variants
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This paper gives an overview on and summarizes existing complexity and algorithmic results of some variants of the Stable Marriage and the Stable Roommates problems. The last section defines a list of stable matching problems mentioned in the paper. If you find any corrections, suggestions, new or missing results, please send them to jiehua.chen2@gmail.com.
fields
cs.GT 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Perspectives on Unsolvability in the Roommates Problem
Random Stable Roommates instances are typically nearly solvable: they have few odd cycles that block stability, and the stable matchings or partitions they admit are usually few, which makes many NP-hard optimization problems easy in practice.