Linear programming brings marital bliss (Q1122480): Difference between revisions

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.