Linear programming brings marital bliss (Q1122480): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:17, 5 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