welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

location: ProblemsDescription / StableMarriageProblem

Stable Marriage Problem

Contents

  1. Stable Marriage Problem
    1. Problem Description
    2. Input format
    3. Output format
    4. Example
    5. Author(s)
    6. References

Problem Description

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

The stable marriage problem (SMP) is the problem of finding a stable matching mapping men to women. Stability in a matching requires that whenever there is no element A of the first matched set that prefers an element B (that it's not matched to) of the second matched set, and at the same time B also prefers A over the one B is matched with.

SMP has several practical applications, as well as several variants. The variant proposed here is known to be polynomially solvable.

Input format

Output format

Example

Author(s)

References