近似算法是处理难解的组合优化问题的一个非常重要和有效的方法。它可以在多项式时间内求得问题的一个解，并使其目标函数值与最优解的目标函数值之比不超过一个常数。本书将通过大量具有代表性的组合优化问题，介绍近似算法设计和分析中的三种主要方法：贪婪算法、限制方法和松弛方法；所讨论的问题来源于不同的研究和应用领域，其中包括通信网络设计、光纤网络、无线自组织网络和传感器网络、生物信息学、社会网络、工业工程和信息管理系统等。此外，本书还将介绍有关组合优化问题不可近似性的一些基本结果。本书的每一章后面都配有相关内容的习题和历史注记。
本书可作为计算机科学和运筹学专业高年级本科生和研究生的近似算法课程的教材，亦可作为相关研究领域科研人员的参考书。
- 目录
- 前辅文
- 第一章 引言
- 1.1 “芝麻, 开门!”
- 1.2 近似算法的设计技巧
- 1.3 启发式算法与近似算法
- 1.4 计算复杂性的术语
- 1.5 NP-完全问题
- 1.6 性能比
- 习题
- 历史注记
- 第二章 贪婪策略
- 2.1 独立系统
- 2.2 拟阵
- 2.3 权函数的四边形条件
- 2.4 次模势函数
- 2.5 应用
- 2.6 非次模势函数
- 习题
- 历史注记
- 第三章 限制
- 3.1 斯坦纳树和生成树
- 3.2 k-限制斯坦纳树
- 3.3 贪婪k-限制斯坦纳树
- 3.4 最小生成树的应用
- 3.5 种系进化树同步
- 习题
- 历史注记
- 第四章 划分
- 4.1 划分与移位
- 4.2 边界区域
- 4.3 多层划分
- 4.4 双重划分
- 4.5 树划分
- 习题
- 历史注记
- 第五章 断切
- 5.1 矩形划分
- 5.2 1-断切
- 5.3 m-断切
- 5.4 接口
- 5.5 四叉树划分与补缀
- 5.6 两阶段接口
- 习题
- 历史注记
- 第六章 松弛
- 6.1 有向哈密顿圈和超串
- 6.2 两阶段贪婪近似算法
- 6.3 单位圆盘图上连通控制集
- 6.4 有向图中的强连通控制集
- 6.5 光纤网络中的多播路由
- 6.6 关于松弛与限制的附记
- 习题
- 历史注记
- 第七章 线性规划
- 7.1 基本性质
- 7.2 单纯形法
- 7.3 组合舍入
- 7.4 管输舍入
- 7.5 迭代舍入
- 7.6 随机舍入
- 习题
- 历史注记
- 第八章 原始对偶方案与局部比值法
- 8.1 对偶理论和原始对偶方案
- 8.2 广义覆盖
- 8.3 网络设计
- 8.4 局部比值法
- 8.5 再论等价性
- 习题
- 历史注记
- 第九章 半定规划
- 9.1 谱面体
- 9.2 半定规划
- 9.3 超平面舍入
- 9.4 旋转向量
- 9.5 多元正交舍入
- 习题
- 历史注记
- 第十章 不可近似性
- 10.1 具有间隙的多一归约
- 10.2 间隙放大与保持
- 10.3 APX-完全性
- 10.4 概率可验证明定理
- 10.5 (½ ln n)-不可近似性
- 10.6 nc-不可近似性
- 习题
- 历史注记
- 参考文献
- 名词索引(汉英对照)
