《近似算法的设计与分析》分为五个部分：首先，在第一部分，即第一章，我们简明扼要地介绍NP—完全性和近似算法的概念。在第二部分，也就是第二章，我们对贪婪算法进行深人的分析，包括以次模函数为势函数的贪婪算法和以非次模函数为势函数的贪婪算法。第三部分包含三章：第三章、第四章和第五章。在这三章中我们讨论多种限制方法，其中包含用于处理几何问题的划分和断切方法。第四部分包含第六章、第七章、第八章和第九章。在这四章中我们主要讨论松弛方法。在第六章中我们对松弛方法进行一般性的讨论以后，在紧接着的三章中，讨论基于线性和半定规划的近似算法设计，包括原始对偶方案和与之等价的局部比值方法。在最后一部分，即第十章，我们介绍应用NP—完全性理论的近期成果所取得的各种不可近似性结果。

Discrete optimization problems are everywhere, from traditional operations research planning (scheduling, facility location and network design); to computer science databases; to advertising issues in viral marketing. Yet most such problems are NP-hard; unless P = NP, there are no efficient algorithms to find optimal solutions. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions. The book is organized around central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization. Each chapter in the first section is devoted to a single algorithmic technique applied to several different problems, with more sophisticated treatment in the second section. The book also covers methods for proving that optimization problems are hard to approximate. Designed as a textbook for graduate-level algorithm courses, it will also serve as a reference for researchers interested in the heuristic solution of discrete optimization problems.