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)

This is a very stimulating book! -- N. G. de Bruijn, Mededelingen van het wiskundig Genootschap (October 1977)
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)
This remarkably well written monograph, through its clarity of expression and elegance of style, certainly achieves its aims and more. ... Anyone would enjoy reading this book. If one had to learn French first, it would be worth the effort. -- J.-L. Lassez, Computing Reviews (June 1979)
This short book will provide extremely enjoyable reading to anyone with an interest in discrete mathematics and algorithm design. -- Fabrizio Luccio, in Mathematical Reviews (1980)
The text provides many interesting examples and problems for students to study while learning the topic of algorithm analysis. -- Timothy H. McNicholl, SIGACT News (March 1999)

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

A Russian translation by Olga Kashina and Eduard Lerner will soon be published by the Moscow Center for Continuous Mathematical Education.

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

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 (3576 bytes) or the errata file in DVI format (4484 bytes) or the errata file in compressed PostScript format (23958 bytes); the latter files were generated by the TeX file. (Last updated 24 November 2023.)

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 (2257 bytes) or the errata file in DVI format (3028 bytes) or the errata file in compressed PostScript format (18297 bytes); the latter files were generated by the TeX file. (Last updated 19 Feb 2015.)

With these corrections, I hope the book is now error-free. But (sigh) it probably isn't. Therefore I will gratefully deposit 0x$1.00 ($2.56) to the account of 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 1B, Stanford University, Stanford, CA 94305-9015 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.

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

Valid HTML 4.01 Transitional