Stable roommates problem

Stable roommates problem

In mathematics, especially in the fields of game theory and combinatorics, the stable roommate problem (SRP) is the problem of finding a stable matching — a matching in which there is no pair of elements, each from a different matched set, where each member of the pair prefers the other to their match. This is different from the stable marriage problem in that the stable roommates problem does not require that a set is broken up into male and female subsets. Any person can prefer anyone in the same set.

It is commonly stated as:: In a given instance of the Stable Roommates problem (SRP), each of "2n" participants ranks the others in strict order of preference. A matching is a set of "n" disjoint (unordered) pairs of participants. A matching "M" in an instance of SRP is stable if there are no two participants "x" and "y", each of whom prefers the other to his partner in "M". Such a pair is said to block "M", or to be a blocking pair with respect to "M".

olution

Algorithm

An efficient algorithm was given in harv|Irving|1985.

Applications

References

*citation | title=An efficient algorithm for the "stable roommates" problem | journal = Journal of Algorithms | issn=01966774 | volume=6 | number=4 | year=1985 | pages=577-595 | first1=Robert W. | last1=Irving | doi=10.1016/0196-6774(85)90033-1
*citation | title=The Stable Roommates Problem with Ties | first1=Robert W. | last1=Irving | first2=David F. | last2=Manlove | journal=Journal of Algorithms | issn=01966774 | volume=43 | number=1 | pages=85-105 | year=2002 | url=http://eprints.gla.ac.uk/11/01/SRT.pdf | doi=10.1006/jagm.2002.1219


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Stable marriage problem — In mathematics, the stable marriage problem (SMP) is the problem of finding a stable matching mdash; a matching in which no element of the first matched set prefers an element of the second matched set that also prefers the first element.It is… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Roommate — A roommate is a person with whom one shares a residence who is not a relative or significant other. Synonyms include suitemate, housemate, or flatmate ( flat : the usual term in British English for an apartment). In the UK, the term roommate… …   Wikipedia

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • Sweet Valley High — Author Francine Pascal Country United States Language English Genre Children s literature Published 1983 …   Wikipedia

  • performing arts — arts or skills that require public performance, as acting, singing, or dancing. [1945 50] * * * ▪ 2009 Introduction Music Classical.       The last vestiges of the Cold War seemed to thaw for a moment on Feb. 26, 2008, when the unfamiliar strains …   Universalium

  • LGBT movements in the United States — comprise an interwoven history of lesbian, gay, bisexual and transgender social and political movements in the United States of America, beginning in the early 20th century. They have been influential worldwide in achieving social progress for… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”