1987/02/01 by Dan Gusfield · 5 citations
Economics, Econometrics and Finance · Computer Science · #Game Theory and Voting Systems #Complexity and Algorithms in Graphs #Advanced Graph Theory Research
paper · doi:10.1137/0216010
The stable marriage problem is a well-known problem of matching n men to n women to achieve a certain type of “stability;” the O(n2 ) time Gale-Shapley [GS] algorithm for finding two particular, but extreme, stable marriages (out of a possibly exponential number of stable marriages) is also well known. In this paper we consider four problems concerned with finding information about the set of all stable marriages, and with finding stable marriages other than those obtained by the Gale-Shapley algorithm. In particular, we give an O(n2 ) time algorithm which, for any problem instance of n men and n women, finds every man–woman pair that is contained in at least one stable marriage; we show that the same algorithm finds all the “rotations” for the problem instance in O(n2 ) time; we give an O(n2 + n|S|) time and O(n2 ) space bounded algorithm (which is time and space optimal) to enumerate all stable marriages, where S is the set of them; and we give an O(n2 ) time algorithm to find the minimum regret stable marriage (the best marriage, as measured by the person who is worst off in it). We believe the previous best time bounds for these problems are respectively O(n4 ) (from a related problem in [K]), O(n3 ) [ILG], O(n3 |S|) [K] and O(n4) [K]. The basic idea leading to the improved running times is to exploit theorems about the structure of stable marriages in order to avoid back-up and duplicated work inherent in earlier algorithms.