The Design of Approximation Algorithms

Citation

Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press. Free electronic edition from the authors: https://www.designofapproxalgs.com/download.php

Chapter Summary

The book is organized by algorithmic technique rather than by problem. Chapter 1 applies several techniques to a single problem, Part I (Chapters 1 to 8) gives one introductory chapter per technique, and Part II (Chapters 9 to 15) returns to each technique in the same order with more demanding applications. Chapters 16 and 17 and two appendices close the book. Chapters end with exercises and chapter notes that point to the literature.

Chapter 1: An introduction to approximation algorithms

Explains why approximation algorithms are studied, defines performance guarantees and approximation schemes, and notes that some problems admit no good approximation at all. It then treats the set cover problem five ways: deterministic rounding of a linear program, rounding a dual solution, the primal-dual method, a greedy algorithm and randomized rounding. The authors introduce the linear programming vocabulary here.

Chapter 2: Greedy algorithms and local search

Contrasts greedy and local search algorithms. Problems include scheduling with deadlines on a single machine, the k-center problem (with a hardness result showing that a factor below 2 would imply P = NP), scheduling on identical parallel machines, the metric traveling salesman problem (nearest addition, double tree and Christofides' algorithm), maximizing float in bank accounts, minimum-degree spanning trees and edge coloring.

Chapter 3: Rounding data and dynamic programming

Uses dynamic programming on rounded inputs to obtain approximation schemes for the knapsack problem, for scheduling on identical parallel machines and for bin packing.

Chapter 4: Deterministic rounding of linear programs

Rounds fractional LP solutions deterministically. Applications are minimizing (weighted) completion times on a single machine, the prize-collecting Steiner tree problem, uncapacitated facility location and bin packing. A section explains how large linear programs can be solved in polynomial time with the ellipsoid method.

Chapter 5: Random sampling and randomized rounding of linear programs

Starts with simple randomized algorithms for MAX SAT and MAX CUT, derandomization, biased coins and randomized rounding, then non-linear rounding and choosing the better of two solutions. Further applications are prize-collecting Steiner tree, facility location, single-machine scheduling with release dates, Chernoff bounds and integer multicommodity flows, and coloring dense 3-colorable graphs.

Chapter 6: Randomized rounding of semidefinite programs

Introduces semidefinite programming and rounding with a random hyperplane. Applications are finding large cuts, approximating quadratic programs, correlation clustering and coloring 3-colorable graphs.

Chapter 7: The primal-dual method

Develops the method through principles illustrated by a sequence of problems: the set cover problem reviewed, feedback vertex set, shortest s-t paths, the generalized Steiner tree problem, the minimum knapsack problem, then uncapacitated facility location and k-median with Lagrangean relaxation.

Chapter 8: Cuts and metrics

Treats cut problems through metrics and linear programs: multiway cut (a minimum-cut-based algorithm and an LP rounding algorithm), multicut, balanced cuts, probabilistic approximation of metrics by tree metrics, with buy-at-bulk network design as an application, and spreading metrics for linear arrangement.

Chapters 9–10: Further uses of greedy and local search algorithms; Further uses of rounding data and dynamic programming

Chapter 9 revisits local search for minimum-degree spanning trees, with a result within 1 of the optimum, and develops local search and greedy algorithms for facility location and the k-median problem. Chapter 10 gives approximation schemes for the Euclidean traveling salesman problem, using dynamic programming over a recursive division of the plane, and for maximum independent set in planar graphs.

Chapters 11–12: Further uses of deterministic rounding of linear programs; Further uses of random sampling and randomized rounding of linear programs

Chapter 11 covers the generalized assignment problem, minimum-cost bounded-degree spanning trees and survivable network design with iterated rounding, building on basic feasible solutions. Chapter 12 returns to facility location with a combined randomized algorithm, then the single-source rent-or-buy problem, the Steiner tree problem and finding a large cut in a dense graph.

Chapters 13–15: Further uses of semidefinite programs, the primal-dual method, and cuts and metrics

Chapter 13 extends the semidefinite analysis to quadratic programs and 3-colorable graphs using properties of the normal distribution, and adds unique games. Chapter 14 gives primal-dual 2-approximation algorithms for prize-collecting Steiner tree and feedback vertex set. Chapter 15 covers low-distortion embeddings and sparsest cut, oblivious routing, cut-tree packings, minimum bisection and the uniform sparsest cut problem; its last section is the book's longest and most complicated proof.

Chapter 16: Techniques in proving the hardness of approximation

A relatively brief survey of hardness proofs: reductions from NP-complete problems, approximation-preserving reductions, reductions from probabilistically checkable proofs, from label cover and from unique games.

Chapter 17: Open Problems

A list of open questions, starting with the unique games conjecture and including the metric traveling salesman problem and its asymmetric variant.

Appendices A–B: Linear programming; NP-completeness

Short reviews of the linear programming and complexity background that the main text uses.

Key Concepts

Chapters 1–3: Foundations

• Performance guarantee: a polynomial-time algorithm is an alpha-approximation if its solution is within factor alpha of the optimum on every instance.
• Approximation scheme (PTAS): a family of algorithms achieving 1 plus or minus epsilon for any fixed epsilon.
• Local search and greedy construction: building or improving a solution by locally best choices.

Chapters 4–8: LP, SDP, primal-dual and metrics

• LP relaxation and rounding: solving a fractional version of an integer program and converting it to an integral solution.
• Randomized rounding and derandomization: random choices analyzed in expectation, then removed by conditional expectations.
• Primal-dual method: constructing a feasible dual solution alongside a primal one to bound the cost.
• Tree metrics: approximating a general metric by random trees at a logarithmic loss.

Chapters 9–17: Extensions and limits

• Iterated rounding: repeatedly solving an LP and fixing variables, used for degree-bounded and survivable network design.
• Integrality gap: the gap between an integer program and its relaxation, limiting what a given formulation can prove.
• Approximation-preserving reduction and unique games conjecture: tools for hardness results.

Critical Analysis

Strengths

• Organized around technique. Because each technique gets its own chapter, readers learn when to reach for rounding, primal-dual or local search, and the repeated return to facility location, prize-collecting Steiner tree, bin packing and maximum cut shows how better tools improve a result.
• A unified view through linear programming. The preface says LP and integer programming are treated as central, and Appendix A and Chapter 1 supply the vocabulary for readers from computer science.
• Designed for teaching. The text grew out of courses taught several times, restricts itself to results simple enough for the classroom, and ends each chapter with exercises and notes.
• Honest about hardness. Hardness appears already in Chapter 1 and in Chapter 2, and Chapter 16 and the open problems chapter explain what cannot be improved.

Limitations

• Prerequisites are real. The preface assumes a prior algorithms course, comfort with proofs, basic probability and some knowledge of NP-completeness; semidefinite programming also requires basic linear algebra. The few NP-completeness reductions in the main text can be skipped, according to the preface.
• Hardness is only a survey. The authors say another book could be written on hardness of approximation, so Chapter 16 is brief.
• Some material is dated. The Open Problems chapter reflects the state of the field in 2010 and mentions results announced but not yet published.
• Dense Part II. Part II is not introductory; the Arora–Rao–Vazirani proof in Chapter 15 is, in the preface's words, the most lengthy and complicated of the book.

Where It Fits in the Course

Within the algorithms course list, this book is a graduate specialization following a general algorithms text such as Introduction to Algorithms. Vazirani's Approximation Algorithms is the closest alternative, also a detailed treatment of techniques for NP-hard problems; Williamson and Shmoys organizes by technique and returns to the same problems, and by the authors' own account gives more coverage to scheduling and semidefinite programming.

Mitzenmacher and Upfal's Probability and Computing is a useful companion for the probabilistic chapters (5, 6, 12 and 13): it develops Chernoff bounds and the probabilistic method in depth. The more applied books in the list, such as The Algorithm Design Manual, Algorithms Illuminated and Algorithms Unlocked, address design and implementation and do not replace it.

How to Use This Book

The book targets graduate students and researchers starting in approximation algorithms. A first course can follow Part I in order: Chapter 1 gives the whole picture on set cover, Chapters 2 and 3 need little beyond algorithms, and Chapters 4, 5 and 7 develop the LP-based methods. Chapter 6 needs linear algebra, and Chapter 8 combines LPs with metric ideas.

From Part II, read the chapter that matches each Part I technique when you want sharper results: Chapter 9 and Section 11.1 are good first stops, and Chapter 16 gives the hardness background. Do at least a few exercises per chapter, and use the chapter notes to find the original papers.

Edition and Sources

This guide is based on the free electronic-only edition on the authors' website, published with the permission of Cambridge University Press. That file is the manuscript submitted to the publisher; the printed edition has different formatting and small corrections. It draws on the preface, the table of contents, the opening of every chapter, the concluding chapters and the appendices.