文档介绍：The Design of
Approximation Algorithms
David P. Williamson
David B. Shmoys
Copyright ⃝c 2010 by David P. Williamson and David B. Shmoys. All rights reserved. To be
published by Cambridge University Press.
2
This electronic-only manuscript is published on h the permis-
sion of Cambridge University Press. One copy per user may be taken for personal use only
and any other use you wish to make of the work is subject to the permission of Cambridge
University Press (rights@). You may not post this file on any other website.
Electronic web edition. Copyright 2010 by David P. Williamson and David B. Shmoys.
To be published by Cambridge University Press
Preface
This book is designed to be a textbook for graduate-level courses in approximation algorithms.
After some experience teaching minicourses in the area in the mid-90s, we sat down and wrote
out an outline of the book. Then I (DPW), at the time an IBM Research Staff Member, taught
several iterations of the course following the outline we had devised, in Columbia University’s
Industrial Engineering and Operations Research department in Spring 1998, in Cornell Uni-
versity’s School of Operations Research and Industrial Engineering in Fall 1998, and at the
Massachusetts Institute of Technology’s Laboratory puter Science in Spring 2000. The
lecture notes from these courses were made available, and we got enough positive feedback on
them from students and from professors teaching such courses elsewhere that we felt we were
on the right track. Since then, there have been many exciting developments in the area, and we
have added many of them into our book; I taught additional iterations of the course at Cornell
in Fall 2006 and Fall 2009 (this time as a Cornell faculty member) in order to field test some
of the writing of the newer results.
The courses were developed for students who have already had a class, undergraduate or
graduate, in algorithms, and who fortable with the idea of mathematical