Small random instances of the stable roommates problem

DOI10.1088/1742-5468/2015/06/P06034MaRDI QIDQ3302312zbMATH OpenOpenAlexFDO

Authors S. Mertens

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.06635

Mathematics Subject Classification ID

Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Abstract: Let $p_n$ denote the probability that a random instance of the stable roommates problem of size $n$ admits a solution. We derive an explicit formula for $p_n$ and compute exact values of $p_n$ for $nleq12$.

Recommendations

• An upper bound for the solvability probability of a random stable roommates instance
• The Average Number of Stable Matchings
• Stable roommates problem with random preferences
• The ``stable roommates problem with random preferences
• On the likely number of solutions for the stable marriage problem

Cites work

• A necessary and sufficient condition for the existence of a complete stable matching
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Beauty and distance in the stable marriage problem
• College Admissions and the Stability of Marriage
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• Random stable matchings
• Stable roommates problem with random preferences
• The ``stable roommates problem with random preferences
• The On-Line Encyclopedia of Integer Sequences

Cited in

(5)

• The Stable Roommates Problem with Short Lists
• Stable roommates problem with random preferences
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• An upper bound for the solvability probability of a random stable roommates instance
• A note on roommate problems with a limited number of rooms

Describes a project that uses

Uses Software

• Mathematica
• OEIS

This page was built for publication: Small random instances of the stable roommates problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302312)