On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
From MaRDI portal
Publication:4289306
DOI10.1017/S0963548300000481zbMATH Open0793.60007OpenAlexW2115159265MaRDI QIDQ4289306FDOQ4289306
Authors: Boris Pittel 
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
Recommendations
- The ``stable roommates problem with random preferences
- Approximation and Online Algorithms
- Random paths to \(P\)-stability in the roommate problem
- An efficient algorithm for the “stable roommates” problem
- On a generalization of the stable roommates problem
- Random paths to stability in the roommate problem
- Small random instances of the stable roommates problem
- An approach to robustness in the stable roommates problem and its comparison with the stable marriage problem
- ``Almost stable matchings in the roommates problem with bounded preference lists
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05)
Cites Work
- Probability Inequalities for Sums of Bounded Random Variables
- Title not available (Why is that?)
- Title not available (Why is that?)
- College Admissions and the Stability of Marriage
- 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
- On the existence of a factor of degree one of a connected random graph
- Title not available (Why is that?)
- Laws of the iterated logarithm for order statistics of uniform spacings
- A necessary and sufficient condition for the existence of a complete stable matching
- An efficient algorithm for the “stable roommates” problem
- The Average Number of Stable Matchings
- Stable husbands
- On likely solutions of a stable marriage problem
- A log log law for maximal uniform spacings
- An analysis of the stable marriage assignment algorithm
Cited In (11)
- An upper bound for the solvability probability of a random stable roommates instance
- Random stable matchings
- The ``stable roommates problem with random preferences
- One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences
- On the likely number of solutions for the stable marriage problem
- On the stable matchings that can be reached when the agents go marching in one by one
- On random exchange-stable matchings
- On random stable partitions
- Stable roommates problem with random preferences
- Small random instances of the stable roommates problem
- On likely solutions of a stable marriage problem
This page was built for publication: On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4289306)
