On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm

DOI10.1017/S0963548300000481MaRDI QIDQ4289306zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

stable matchingIrving's algorithmstable marriages problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05)

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

Cites work

• scientific article; zbMATH DE number 1194806 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 48303 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A log log law for maximal uniform spacings
• A necessary and sufficient condition for the existence of a complete stable matching
• An analysis of the stable marriage assignment algorithm
• An efficient algorithm for the “stable roommates” problem
• College Admissions and the Stability of Marriage
• Laws of the iterated logarithm for order statistics of uniform spacings
• On a Class of Problems Related to the Random Division of an Interval
• On likely solutions of a stable marriage problem
• On the existence of a factor of degree one of a connected random graph
• Probability Inequalities for Sums of Bounded Random Variables
• Stable husbands
• The Average Number of Stable Matchings

Cited in

(11)

• An upper bound for the solvability probability of a random stable roommates instance
• The ``stable roommates problem with random preferences
• Random stable matchings
• 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)