The Design of Approximation Algorithms

Free eBook “The Design of Approximation Algorithms” by David P. Williamson and David B. Shmoys. The book is organized around several central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization.

Book Description

Each chapter in the first part of the book is devoted to a single algorithmic technique, which is then applied to several different problems. The second part revisits the techniques, but offers more sophisticated treatments of them. The book also covers methods for proving that optimization problems are hard to approximate. Designed as a textbook for graduate-level algorithms courses, the book will also serve as a reference for researchers who are interested in the heuristic solution of discrete optimization problems.

Table of Contents

• An introduction to approximation algorithms
• Greedy algorithms and local search
• Rounding data and dynamic programming
• Deterministic rounding of linear programs
• Random sampling and randomized rounding of linear programs
• Randomized rounding of semidefinite programs
• The primal-dual method
• Cuts and metrics
• Further uses of greedy and local search algorithms
• Further uses of rounding data and dynamic programming
• Further uses of deterministic rounding of linear programs
• Further uses of random sampling and randomized rounding of linear programs
• Further uses of randomized rounding of semidefinite programs
• Further uses of the primal-dual method
• Further uses of cuts and metrics
• Techniques in proving the hardness of approximation
• Open Problems

Download Free PDF / Read Online