The well-known stable marriage problem seeks to achieve various “stable” matchings of n men to m women. This paper presents several algorithms that are faster than previously known because they exploit certain structural theorems to avoid redundant work. For instance, an algorithm to find a “minimum regret stable marriage” is given that improves known time complexity to O(n²) from O(n⁴). The open problem of how best to check that a marriage is stable is also briefly discussed. (A marriage (matching) is stable when no unrealized match exists that both the man and the woman prefer to their matches in the actual marriage.)

The paper is well written and contains an excellent summary and bibliography of previous work in the area. Thus, it may be read by novices as well as experts interested in this fascinating combinatorial problem.