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

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

1 引言
  1.1 确定OPT的下界
   1.1.1 基数顶点覆盖的近似算法
   1.1.2 能够改进近似保证吗？
  1.2 有好刻画的问题和最小最大关系
  1.3 练习
  1.4 注释
第一部分 组合算法
  2 集合覆盖
   2.1 贪婪算法
   2.2 分层
   2.3 应用于最短超字符串
   2.4 练习
   2.5 注释
  3 施泰纳树和旅行商
   3.1 度量施泰纳树
   3.2 度量旅行商
   3.3 练习
   3.4 注释
  4 多向割和k-割
   4.1 多向割问题
   4.2 最小k-割问题
   4.3 练习
   4.4 注释
  5 k-中心
   5.1 参数修剪应用于度量k-中心
   5.2 加权形式
   5.3 练习
   5.4 注释
  6 反馈顶点集
   6.1 圈加权图
   6.2 分层应用于反馈顶点集
   6.3 练习
   6.4 注释
  7 最短超字符串
   7.1 因子4算法
   7.2 改进到因子3
   7.2.1 达到最优压缩的一半
   7.3 练习
   7.4 注释
  8 背包
   8.1 背包的伪多项式时间算法
   8.2 背包的FPTAS
   8.3 强NP-难解性和FPTAS的存在性
   8.3.1 FPTAS是最值得找的近似算法吗？
   8.4 练习
   8.5 注释
  9 装箱问题
   9.1 渐近PTAS
   9.2 练习
   9.3 注释
  10 最小时间跨度排序
   10.1 因子2算法
   10.2 最小时间跨度的PTAS
   10.3 练习
   10.4 注释
  11 欧几里得旅行商
   11.1算法
   11.2 正确性证明
   11.3 练习
   11.4 注释
第二部分 基于线性规划的算法
  12 线性规划对偶介绍
   12.1 线性规划对偶定理
   12.2 最小最大关系和线性规划对偶
   12.3 两个基本的算法设计技术
   12.4 练习
   12.5 注释
  13 用对偶拟合分析集合覆盖
   13.1 对贪婪集合覆盖算法进行基于对偶拟合的分析
   13.2 集合覆盖的推广
   13.2.1 对偶拟合应用于有约束的集合多次覆盖
   13.3 练习
   13.4 注释
  14 舍入应用于集合覆盖
   14.1 简单的舍入算法
   14.2 随机舍入
   14.3 顶点覆盖的半整性
   14.4 练习
   14.5 注释
  15 对集合覆盖使用原始对偶模式
   15.1 模式概述
   15.2 对集合覆盖使用原始对偶模式
   15.3 练习
   15.4 注释
  16 最大可满足性
   16.1 处理大子句
   16.2 使用条件期望方法来去随机化
   16.3 使用线性规划舍入来处理小子句
   16.4 3/4因子算法
   16.5 练习
   16.6 注释
  17 无关平行机排序
   17.1 线性规划背景下的参数修剪
   17.2 极点解的性质
   17.3算法
   17.4 极点解的附加性质
   17.5 练习
   17.6 注释
  18 树的多割和树的整数多商品流
   18.1 问题和它们的线性规划松弛
   18.2 基于原始对偶模式的算法
   18.3 练习
   18.4 注释
  19 多向割
   19.1 令人感兴趣的线性规划松弛
   19.2 随机舍入算法
   19.3 结点多向割的半整性
   19.4 练习
   19.5 注释
  20 一般图的多割
   20.1 和多商品流
   20.2 基于线性规划舍入的算法
   20.3 紧例子
   20.4 多割的一些应用
   20.5 练习
   20.6 注释
  21 最稀疏割
   21.1 需求多商品流
   21.2 线性规划模型
   21.3 度量,割填装和?1-可嵌入性
   21.4 度量的低失真?1-嵌入
   21.5 基于线性规划舍入的算法
   21.6 应用
  22 施泰纳森林
   22.1 线性规划松弛和对偶
   22.2 同步原始对偶模式
   22.3 分析
   22.4 练习
   22.5 注释
  23 施泰纳网络
   23.1 线性规划松弛和半整性
   23.2 迭代舍入技术
   23.3 刻画极点解
   23.4 计数论证
   23.5 练习
   23.6 注释
  24 设施定位
   24.1 对偶的直观理解
   24.2 松弛原始互补松弛条件
   24.3 基于原始对偶模式的算法
   24.4 分析
   24.5 练习
   24.6 注释
  25 k-中位点
   25.1 线性规划松弛和对偶
   25.2 高级想法
   25.3 随机舍入
   25.4 近似算法的拉格朗日松弛技术
   25.5 练习
   25.6 注释
  26 半定规划
   26.1 严格二次规划和向量规划
   26.2 半正定矩阵的性质
   26.3 半定规划问题
   26.4 随机舍入算法
   26.5 对MAX-2SAT改进近似保证
   26.6 练习
   26.7 注释
第三部分 其他主题
  27 最短向量
   27.1 基、行列式和正交性亏量
   27.2 欧几里得算法和高斯算法
   27.3 使用格拉姆?施密特正交化确定OPT的下界
   27.4 推广到n维空间
   27.5 对偶格和它的算法应用
   27.6 练习
   27.7 注释
  28 计数问题
   28.1 计数DNF解
   28.2 网络可靠性
   28.3 练习
   28.4 注释
  29 近似困难性
   29.1 归约、间隙和困难性因子
   29.2 PCP定理
   29.3 MAX-3SAT的困难性
   29.4 变量出现次数有限的MAX-3SAT的困难性
   29.5 顶点覆盖和施泰纳树的困难性
   29.6 团的困难性
   29.7 集合覆盖的困难性
   29.8 练习
   29.9 注释
  30 未解决的问题
   30.1 有常数因子算法的问题
   30.2 其他最优化问题
   30.3 计数问题
   30.4 注释
附录
  A 为算法设计者概述复杂性理论
   A.1 证据和NP类
   A.2 归约和NP-完全性
   A.3 NP-最优化问题和近似算法
   A.4 随机复杂类
   A.5 自可归约性
   A.6 注释
  B 概率论的基本事实
   B.1 期望和矩
   B.2 均值偏差
   B.3 基本分布
   B.4 注释
参考文献
问题索引
主题索引

国外信息技术优秀图书选译