Donald Bren School of Information and Computer Sciences

We give an O(n^3 √logn) time algorithm for the optimal stable marriage problem. This algorithm finds a stable marriage that minimizes an objective function defined over all stable marriages in a given problem instance.

Irving, Leather, and Gusfield have previously provided a solution to this problem that runs in O(n^4) time [ILG87]. In addition, Feder has claimed that an O(n^3 log n) time algorithm exists [F89]. Our result is an asymptotic improvement over both cases.

As part of our solution, we solve a special blue-red matching problem, and illustrate a technique for simulating Hopcroft and Karp's maximum-matching algorithm [HK73] on the transitive closure of a graph.