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

DOI10.1017/S0963548300000481zbMath0793.60007MaRDI QIDQ4289306

Boris G. 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 matching; Irving's algorithm; stable marriages problem

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

60C05: Combinatorial probability

Related Items

An upper bound for the solvability probability of a random stable roommates instance, Random stable matchings, On random exchange-stable matchings, On random stable partitions, 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

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