Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms

by Donald Ervin Knuth

The book uses the appealing theory of stable marriage to introduce and illustrate a variety of important concepts and techniques of computer science and data structures, control structures, combinatorics, probability, analysis, algebra, and especially the analysis of algorithms. The presentation is elementary, and the topics are interesting to nonspecialists. The theory is quite beautiful and developing rapidly. Exercises with answers, an annotated bibliography, and research problems are included. The text would be appropriate as supplementary reading for undergraduate research seminars or courses in algorithmic analysis and for graduate courses in combinatorial algorithms, operations research, economics, or analysis of algorithms. Donald E. Knuth is one of the most prominent figures of modern computer science. His works in The Art of Computer Programming are classic. He is also renowned for his development of TeX and METAFONT. In 1996, Knuth won the prestigious Kyoto Prize, considered to be the nearest equivalent to a Nobel Prize in computer science.

Genres: Mathematics

74 pages, Paperback

First published October 1, 1996

About the author

Donald Ervin Knuth, born January 10th 1938, is a renowned computer scientist and Professor Emeritus of the Art of Computer Programming at Stanford University.

Author of the seminal multi-volume work The Art of Computer Programming ("TAOCP"), Knuth has been called the "father" of the analysis of algorithms, contributing to the development of, and systematizing formal mathematical techniques for, the rigorous analysis of the computational complexity of algorithms, and in the process popularizing asymptotic notation.

In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, and the Computer Modern family of typefaces.

A prolific writer and scholar, Knuth created the WEB/CWEB computer programming systems designed to encourage and facilitate literate programming, and designed the MMIX instruction set architecture.

Reviews

[Maaz Muhammad]

Short, readable. The notation is somewhat anachronistic - no one in the matching literature denotes men and women by upper and lowercase letters anymore, ditto for the preference relations. Knuth proposes some interesting open problems at the end of the book. It would be interesting to see an updated version outlining progress on those problems (I know for example that Roth showed that there are “random paths to stability”). The most interesting result in this book is the lattice structure of stable matchings - interestingly, this was actually devised by John Conway (a hero to many of us who sadly passed away from COVID-19). All in all a great primer of the more combinatorics aspects of the stable marriage problem by the father of algorithmic analysis. Although, for someone interested in learning the important “classical” results in matching, I would strongly recommend Roth and Sotomayor’s “two sided matching”.