Premium
An upper bound for the solvability probability of a random stable roommates instance
Author(s) -
Pittel Boris G.,
Irving Robert W.
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050307
Subject(s) - upper and lower bounds , matching (statistics) , combinatorics , limiting , mathematics , discrete mathematics , statistics , mathematical analysis , mechanical engineering , engineering
It is well‐known that not all instances of the stable roommates problem admit a stable matching. Here we establish the first nontrivial upper bound on the limiting behavior of P n , the probability that a random roommates instance of size n has a stable matching, namely, lim n →∞ P n ⩽ e 1/2 /2 (=0.8244…). © 1994 John Wiley & Sons, Inc.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom