Mariages Stables

et leurs relations avec d'autres problèmes combinatoires par Donald E. Knuth (Montréal: Les Presses de l'Université de Montréal, 1976), 106pp.
(Collection de la Chaire Aisenstadt.)
ISBN 2-7606-0529-9

full text (PDF) scanned by Marcin Anholcer (7.6MB)

An English translation by Martin Goldstein, Stable Marriage and its Relation to Other Combinatorial Problems, has just been published by the American Mathematical Society as volume 10 of the series entitled CRM Proceedings and Lecture Notes.

This booklet, which reproduces seven expository lectures given by the author in November 1975, is a gentle introduction to the analysis of algorithms, using the beautiful theory of stable marriages as a vehicle to explain the basic paradigms of that subject.

Table of Contents (English):

1. Introduction, definitions, and examples
2. Existence of a stable matching; the fundamental algorithm
3. The principle of late binding; coupon collecting
4. Theoretical developments; application to the shortest path problem
5. Hashing; average behavior of the fundamental algorithm
6. Implementations and variants of the fundamental algorithm
7. Research problems

This book is an excellent (and enjoyable) means of sketching a large area of computer science for specialists in other fields: It requires little previous knowledge, but expects of the reader a degree of mathematical facility and a willingness to participate. It is really neither a survey nor an introduction; rather, it is a paradigm, a fairly complete treatment of a single example used as a synopsis of a larger subject. -- Harry Lewis, SIGACT News (Winter 1978)

Errata

For a list of corrections to known errors in the French edition of this book (in English!), you may download either the errata file in plain TeX format (3217 bytes) or the errata file in DVI format (3888 bytes) or the errata file in compressed PostScript format (22830 bytes); the latter files were generated by the TeX file.

For a list of corrections to known errors in the English edition of this book (in English!), you may download either the errata file in plain TeX format (1854 bytes) or the errata file in DVI format (2368 bytes) or the errata file in compressed PostScript format (16479 bytes); the latter files were generated by the TeX file.

With these corrections, I hope the book is now error-free. But (sigh) it probably isn't. Therefore I will gratefully pay $2.56 to the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045 USA. I may not be able to read your message until many months have gone by, because I'm working intensively on The Art of Computer Programming. However, I promise to reply in due time, and to pay your reward with interest compounded from the day you pointed out the error.

DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.

Don Knuth's home page

Don Knuth's other books