The Stable Marriage Problem ― Structure and Algorithms

This book probes the stable marriage problem and its variants as a rich source ofproblems and ideas that illustrate both the design and analysis of efficient algorithms. It coversthe most recent structural and algorithmic work on stable matching problems, simplifies and unifiesmany earlier proofs, strengthens several earlier results, and presents new results and moreefficient algorithms.The authors develop the structure of the set of stable matchings in the stablemarriage problem in a more general and algebraic context than has been done previously; they discussthe problem's structure in terms of rings of sets, which allows many of the most useful features tobe seen as features of a more general set of problems. The relationship between the structure of thestable marriage problem and the more general stable roommates problem is demonstrated, revealingmany commonalities.The results the authors obtain provide an algorithmic response to the practical,and political, problems created by the asymmetry inherent in the Gale Shapley solutions,leading to alternative methods and better compromises than are provided by the Gale Shapley method.And, in contrast to Donald Knuth's earlier work which primarily focused on the application ofmathematics to the analysis of algorithms, this book illustrates the productive and almostinseparable relationship between mathematical insight and the design of efficient algorithms.DanGusfield is Associate Professor of Computer Science at the University of California, Davis. RobertW. Irving is Senior Lecturer in Computing Science at the University of Glasgow. The Stable MarriageProblem is included in the Foundations of Computing Series, edited by Michael Garey and AlbertMeyer.