本书涵盖了获取难解组合最优化问题和计数问题的近似解的主要理论方法。它包括简洁优雅的组合理论，有用又有趣的算法以及组合问题所固有复杂性的深入结果。讲解清晰透彻，练习选取精当，本书必将被所有数学和算法研究者所接受并喜爱。

本书关注近似算法这一重要且适时的主题，写作上乘，内容全面。信广大读者无论是将其用作近似性的入门教材，还是作为近似算法诸多问题的参考资料，都会发现本书极为有用。

本书系统总结了到本世纪初为止近似算法领域的成果，重点关注近似算法的设计与分析，介绍了这个领域中最重要的问题以及所使用的基本方法和思想。全书分为三部分：第一部分使用不同的算法设计技巧给出了下述优化问题的组合近似算法：集合覆盖、施泰纳树和旅行商、多向割和k-割、k-中心、反馈顶点集、最短超字符串、背包、装箱问题、最小时间跨度排序、欧几里得旅行商等。第二部分介绍基于线性规划的近似算法。第三部分包括四个主题：在一个格中找一个最短向量、计数问题的可近似性、基于PCP定理的近似困难性以及未解决的问题等，这些问题都是近似算法领域中的前沿研究内容。

本书可作为计算机科学、应用数学、运筹学、信息科学与网络工程、物流与交通运输、管理科学与工程、生命科学、电子科学与技术等学科专业的研究生及高年级本科生的教学用书，对相关领域的科学研究人员也具有参考价值。

1 引言

第一部分 组合算法

2 集合覆盖

3 施泰纳树和旅行商

4 多向割和k-割

5 k-中心

6 反馈顶点集

7 最短超字符串

8 背包

9 装箱问题

10 最小时间跨度排序

11 欧几里得旅行商

第二部分 基于线性规划的算法

12 线性规划对偶介绍

13 用对偶拟合分析集合覆盖

14 舍入应用于集合覆盖

15 对集合覆盖使用原始对偶模式

16 最大可满足性

17 无关平行机排序

18 树的多割和树的整数多商品流

19 多向割

20 一般图的多割

21 最稀疏割

22 施泰纳森林

23 施泰纳网络

24 设施定位

25 k-中位点

26 半定规划

第三部分 其他主题

27 最短向量

28 计数问题

29 近似困难性

30 未解决的问题

附录

A 为算法设计者概述复杂性理论

B 概率论的基本事实

参考文献

问题索引

主题索引