4 Preface
lems in database and programming language design to advertising issues in viral marketing.
We hope that the book helps researchers understand the techniques available in the area of
approximation algorithms for approaching such problems.
We have taken several particular perspectives in writing the book. The first is that we
wanted to organize the material around certain principles of designing approximation algo-
rithms, around algorithmic ideas that have been used in different ways and applied to different
optimization problems. The title The Design of Approximation Algorithms was carefully cho-
sen. The book is structured around these design techniques. The introduction applies several
of them to a single problem, the set cover problem. The book then splits into two parts. In the
first part, each chapter is devoted to a single algorithmic idea (e.g., “greedy and local search
algorithms,”“rounding data and dynamic programming”), and the idea is then applied to sev-
eral different problems. The second part revisits all of the same algorithmic ideas, but gives
more sophisticated treatments of them; the results covered here are usually much more recent.
The layout allows us to look at several central optimization problems repeatedly throughout
the book, returning to them as a new algorithmic idea leads to a better result than the previous
one. In particular, we revisit such problems as the uncapacitated facility lo cation problem, the
prize-collecting Steiner tree problem, the bin-packing problem, and the maximum cut problem
several times throughout the course of the book.
The second perspective is that we treat linear and integer programming as a central aspect
in the design of approximation algorithms. This perspective is from our background in the
operations research and mathematical programming communities. It is a little unusual in the
computer science community, and students coming from a computer science background may
not be familiar with the basic terminology of linear programming. We introduce the terms we
need in the first chapter, and we include a brief introduction to the area in an app endix.
The third perspective we took in writing the book is that we have limited ourselves to results
that are simple enough for classroom presentation while remaining central to the topic at hand.
Most of the results in the book are ones that we have taught ourselves in class at one point or
another. We bent this rule somewhat in order to cover the recent, exciting work by Arora, Rao,
and Vazirani [22] applying semidefinite programming to the uniform sparsest cut problem. The
proof of this result is the most lengthy and complicated of the book.
We are grateful to a number of people who have given us feedback about the book at various
stages in its writing. We are particularly grateful to James Davis, Lisa Fleischer, Isaac Fung,
Rajiv Gandhi, Igor Gorodezky, Nick Harvey, Anna Karlin, Vijay Kothari, Katherine Lai, Gwen
Spencer, and Anke van Zuylen for very detailed comments on a number of sections of the
book. Additionally, the following people spotted typos, gave us feedback, helped us understand
particular papers, and made useful suggestions: Bruno Abrahao, Hyung-Chan An, Matthew
Andrews, Eliot Anshelevich, Sanjeev Arora, Ashwinkumar B.V., Moses Charikar, Chandra
Chekuri, Joseph Cheriyan, Chao Ding, Dmitriy Drusvyatskiy, Michel Goemans, Sudipto Guha,
Anupam Gupta, Sanjeev Khanna, Lap Chi Lau, Renato Paes Leme, Jan Karel Lenstra, Roman
Rischke, Gennady Samorodnitsky, Daniel Schmand, Jiawei Qian, Yogeshwer Sharma, Viktor
Simjanoski, Mohit Singh,
´
Eva Tardos, Mike Todd, Di Wang, and Ann Williamson. We also
thank a number of anonymous reviewers who made useful comments. Eliot Anshelevich, Joseph
Cheriyan, Lisa Fleischer, Michel Goemans, Nicole Immorlica, and Anna Karlin used various
drafts of the book in their courses on approximation algorithms and gave us useful feedback
about the experience of using the book. We received quite a number of useful comments from the
students in Anna’s class: Benjamin Birnbaum, Punyashloka Biswal, Elisa Celis, Jessica Chang,
Mathias Hallman, Alyssa Joy Harding, Trinh Huynh, Alex Jaffe, Karthik Mohan, Katherine
Moore, Cam Thach Nguyen, Richard Pang, Adrian Sampson, William Austin Webb, and Kevin
Electronic web edition. Copyright 2011 by David P. Williamson and David B. Shmoys.
To be published by Cambridge University Press
