On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
From MaRDI portal
Publication:4289306
DOI10.1017/S0963548300000481zbMath0793.60007OpenAlexW2115159265MaRDI QIDQ4289306
Publication date: 24 May 1994
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548300000481
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05)
Related Items (7)
On random exchange-stable matchings ⋮ An upper bound for the solvability probability of a random stable roommates instance ⋮ One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences ⋮ Small random instances of the stable roommates problem ⋮ On the Likely Number of Solutions for the Stable Marriage Problem ⋮ On random stable partitions ⋮ Random stable matchings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Laws of the iterated logarithm for order statistics of uniform spacings
- A log log law for maximal uniform spacings
- On likely solutions of a stable marriage problem
- A necessary and sufficient condition for the existence of a complete stable matching
- The Average Number of Stable Matchings
- An efficient algorithm for the “stable roommates” problem
- Probability Inequalities for Sums of Bounded Random Variables
- On the existence of a factor of degree one of a connected random graph
- An analysis of the stable marriage assignment algorithm
- Stable husbands
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- On a Class of Problems Related to the Random Division of an Interval
- College Admissions and the Stability of Marriage
This page was built for publication: On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
