Linear programming brings marital bliss (Q1122480): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0167-6377(89)90041-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2121619875 / rank | |||
Normal rank |
Revision as of 21:25, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear programming brings marital bliss |
scientific article |
Statements
Linear programming brings marital bliss (English)
0 references
1989
0 references
The problem of stable marriage was investigated by many authors. \textit{D. Gale} and \textit{L. S. Shapley} [Am. Math. Mon. 69, 9-15 (1962; Zbl 0109.244)], showed that regardless of the individual preferences, a stable matching always exists. \textit{R. Irving}, \textit{P. Leather} and \textit{D. Gusfield} [J. Assoc. Comput. Mach. 34, No.3, 532-543 (1987)] gave an algorithm for finding an optimal stable matching. In this paper, the author shows how to find the optimal stable matching by means of linear programming. This characterization of the stable marriage problem extends Dantzig's remark referred to the linear programming characterization of the bipartite matching problem as the monogamy is the best of all the possible forms of marriage. The author shows that among all forms of marriage monogamous stable marriage is the best.
0 references
assignment
0 references
stable marriage
0 references
optimal stable matching
0 references