Approximation Algorithms

Citation

Vazirani, V. V. (2001). Approximation Algorithms (1st ed.). Springer. (Corrected second printing 2003; softcover reprint 2010.)

Chapter Summary

The book has thirty chapters in three parts, plus two appendices. Almost every chapter is built around one problem, ends with exercises and chapter notes, and keeps its main text short.

Chapter 1: Introduction

Sets out the basic idea of an approximation guarantee and uses vertex cover to show how lower-bounding the optimum (OPT) drives an analysis. It also asks whether a guarantee can be improved and introduces well-characterized problems and min-max relations.

Part I, Chapters 2–4: Set Cover; Steiner Tree and TSP; Multiway Cut and k-Cut

Set cover is treated by the greedy algorithm and by layering, with an application to shortest superstring. Steiner tree and metric TSP follow, including a simple factor-2 algorithm and the improvement to 3/2 for TSP, and then the multiway cut and minimum k-cut problems.

Part I, Chapters 5–7: k-Center; Feedback Vertex Set; Shortest Superstring

k-center is handled by parametric pruning, including a weighted version. Feedback vertex set uses cyclomatic weighted graphs and layering. Shortest superstring gets a factor-4 algorithm, then an improvement to factor 3.

Part I, Chapters 8–11: Knapsack; Bin Packing; Minimum Makespan Scheduling; Euclidean TSP

These chapters are about approximation schemes. Knapsack has a pseudo-polynomial algorithm, an FPTAS and a discussion of strong NP-hardness. Bin packing gets an asymptotic PTAS, makespan scheduling a factor-2 algorithm and a PTAS, and Euclidean TSP an algorithm followed by a proof of correctness.

Part II, Chapters 12–15: LP-Duality and Set Cover

Chapter 12 introduces LP-duality, min-max relations, the two design techniques of the part (rounding and the primal-dual schema) and the integrality gap. Chapters 13–15 then return to set cover three times: dual fitting for the greedy algorithm, rounding (simple and randomized, with half-integrality of vertex cover), and the primal-dual schema.

Part II, Chapters 16–21: Maximum Satisfiability to Sparsest Cut

Maximum satisfiability is attacked by derandomization and LP rounding, leading to a 3/4 factor. Scheduling on unrelated parallel machines uses extreme point solutions. Chapters 18–21 cover multicut in trees, multiway cut, multicut in general graphs and sparsest cut, the last through metrics, cut packings and low-distortion embeddings.

Part II, Chapters 22–26: Steiner Forest to Semidefinite Programming

Steiner forest uses a primal-dual schema with synchronization, and Steiner network uses iterated rounding. Facility location and k-median follow, the latter with a Lagrangian relaxation technique. Chapter 26 introduces semidefinite programming and applies randomized rounding to MAX-2SAT.

Part III, Chapters 27–30: Other Topics

Shortest vector in a lattice (Chapter 27), two counting problems (DNF solutions and network reliability, Chapter 28), hardness of approximation built on the PCP theorem, culminating in a hardness result for set cover (Chapter 29), and a list of open problems (Chapter 30). Appendix A reviews complexity theory for the algorithm designer and Appendix B basic probability.

Key Concepts

Chapters 1–11

• Lower bounding OPT: an approximation factor is proved by comparing the algorithm's output with an easily computed bound on the optimum.
• Layering and parametric pruning: two combinatorial techniques used for set cover, feedback vertex set and k-center.
• PTAS and FPTAS: schemes whose guarantee can be made arbitrarily close to 1, with the knapsack chapter asking when an FPTAS can exist at all.

Chapters 12–26

• LP-duality and integrality gap: the theorem linking a linear program to its dual, and the ratio that limits any analysis based on a given relaxation.
• Dual fitting, rounding, primal-dual schema: three ways of turning an LP relaxation into an algorithm with a guarantee.
• Iterated rounding and semidefinite relaxations: more elaborate rounding methods used for Steiner network and MAX-2SAT.

Chapters 27–30

• Gap reductions and the PCP theorem: the machinery behind hardness-of-approximation results.
• Approximate counting: approximating the number of solutions rather than optimizing over them.

Critical Analysis

Strengths

• Short chapters built around one problem. The preface says individual chapters are kept short and simple, often presenting only the key result, with generalizations pushed into exercises. This makes it easy to read one chapter at a time.
• Exercises and hints. Nearly every chapter has an exercise section and notes, and the preface adds that hints are given for some exercises.
• Techniques are visible in the structure. Part II is organized by technique, and set cover is revisited with greedy, dual fitting, rounding and primal-dual methods, then given a matching hardness result in Chapter 29. Seeing one problem through several lenses is a real teaching aid.
• Self-contained background. Appendices cover complexity theory and probability, and LP, semidefinite programming and lattices are introduced in Chapters 12, 26 and 27.
• Reviewers' verdicts. Mark Jerrum (Mathematical Reviews, 2002) called it possibly the first textbook with extensive and systematic coverage of the topic and praised its copious exercises. Viggo Kann (Zentralblatt MATH, 2003) found the results often easier to follow than the original articles, and Csanád Imreh (Acta Scientiarum Mathematicarum, 2002) judged it usable for a graduate course and by researchers.

Limitations

• A 2001 snapshot. The author writes that the book presents the theory as it stands at the time of writing and expects the picture to change, and the open-problem list is described as centered on issues then in vogue.
• Part I is deliberately varied. The preface admits the combinatorial part may look non-cohesive, because techniques are not categorized tightly. Readers who want a technique-first course will find Part II more systematic.
• Some proofs are taken on trust. Chapter 29 assumes the PCP theorem, which the preface says lacks a simple proof, and the book does not cover Markov chain Monte Carlo methods for counting.
• Material beyond one course. The preface says there is more than twice the material of a semester course, so a reader needs to choose a route.

Where It Fits in the Course

Within this course list, Vazirani is a specialist text. Introduction to Algorithms (Cormen, Leiserson, Rivest and Stein) is the general reference; its Chapter 35 is the approximation-algorithms chapter and its Chapter 34 covers NP-completeness, which Vazirani assumes. Skiena's The Algorithm Design Manual is a practical guide to recognizing and solving algorithmic problems, with approximation among its methods. Roughgarden's Algorithms Illuminated and Cormen's Algorithms Unlocked are gentler introductions to algorithms for readers who are not ready for a graduate text.

The closest comparison is The Design of Approximation Algorithms by Williamson and Shmoys, a graduate text on the same subject, which its page describes as ranging from greedy methods to semidefinite programming with a discussion of theoretical limits. Both books cover the core ground; Vazirani offers short problem-centred chapters and a three-part structure, so the two work well side by side. Probability and Computing by Mitzenmacher et al. is a useful companion for the randomized rounding in Chapters 14, 16 and 26.

How to Use This Book

The book is aimed at advanced undergraduates and graduate students. The preface names an undergraduate algorithms course and the theory of NP-completeness as sufficient preparation for most chapters, and Appendices A and B refresh complexity and probability.

A sensible first route reads Chapter 1, then Chapters 2, 3, 5 and 8–10 of Part I, whose chapters are ordered roughly by increasing difficulty. Continue with Chapters 12–15, which introduce LP-duality and the three LP techniques on a single familiar problem, and then Chapters 16, 17 and 24. Chapters 18–23, 25 and 26 form an optional second pass for readers who want cuts, network design, clustering and semidefinite methods. Chapter 29 can be read after Appendix A by anyone who wants the hardness side. For a general algorithms course, the preface recommends only the first few chapters of Parts I and II as supplementary reading.

Do the exercises: generalizations and related results are placed there, and the chapter notes give the references for going further.