第一章 近似算法基础 #

1.1 近似算法概述 #

1.1.1 近似算法定义与特征 #

1.1.2 近似算法与精确算法比较 #

1.1.3 近似算法的应用场景 #

1.2 性能分析基础 #

1.2.1 近似比定义与计算 #

1.2.2 最坏情况分析 #

1.2.3 平均情况分析 #

1.3 计算复杂性理论基础 #

1.3.1 P、NP和NP完全问题 #

1.3.2 近似难度分类 #

1.3.3 不可近似性理论 #

第二章 经典近似算法技术 #

2.1 贪心算法 #

2.1.1 贪心选择策略 #

2.1.2 集合覆盖问题的贪心近似 #

2.1.3 任务调度问题的贪心近似 #

2.2 线性规划舍入 #

2.2.1 线性规划松弛 #

2.2.2 随机舍入技术 #

2.2.3 确定性舍入方法 #

2.3 局部搜索算法 #

2.3.1 邻域结构设计 #

2.3.2 局部最优与全局最优 #

2.3.3 局部搜索的近似保证 #

2.4 动态规划近似 #

2.4.1 缩放技术 #

2.4.2 状态空间约简 #

2.4.3 近似动态规划框架 #

第三章 组合优化问题的近似算法 #

3.1 覆盖问题 #

3.1.1 顶点覆盖近似算法 #

3.1.2 集合覆盖近似算法 #

3.1.3 边覆盖近似算法 #

3.2 划分问题 #

3.2.1 图划分近似算法 #

3.2.2 装箱问题近似算法 #

3.2.3 聚类问题近似算法 #

3.3 路径与旅行问题 #

3.3.1 旅行商问题近似算法 #

3.3.2 斯坦纳树问题近似算法 #

3.3.3 最短路径问题近似算法 #

3.4 匹配问题 #

3.4.1 最大匹配近似算法 #

3.4.2 稳定匹配近似算法 #

3.4.3 加权匹配近似算法 #

第四章 随机近似算法 #

4.1 随机算法基础 #

4.1.1 随机算法的期望分析 #

4.1.2 概率放大技术 #

4.1.3 随机舍入方法 #

4.2 马尔可夫链蒙特卡洛方法 #

4.2.1 马尔可夫链收敛性 #

4.2.2 混合时间分析 #

4.2.3 在近似计数中的应用 #

4.3 随机游走算法 #

4.3.1 随机游走的基本性质 #

4.3.2 连通性测试 #

4.3.3 图分割的随机算法 #

第五章 在线算法与竞争分析 #

5.1 在线算法基础 #

5.1.1 在线问题模型 #

5.1.2 竞争比定义 #

5.1.3 确定性在线算法 #

5.2 经典在线问题 #

5.2.1 分页算法 #

5.2.2 滑雪租赁问题 #

5.2.3 在线匹配问题 #

5.3 随机在线算法 #

5.3.1 随机化对抗 adversaries #

5.3.2 随机在线算法的竞争比 #

5.3.3 随机舍入在线算法 #

第六章 近似方案与PTAS #

6.1 多项式时间近似方案 #

6.1.1 PTAS定义与性质 #

6.1.2 完全多项式时间近似方案 #

6.1.3 PTAS设计技术 #

6.2 基于动态规划的PTAS #

6.2.1 缩放和舍入 #

6.2.2 状态空间约简 #

6.2.3 多维动态规划 #

6.3 基于局部搜索的PTAS #

6.3.1 k-交换邻域 #

6.3.2 局部搜索收敛性 #

6.3.3 近似方案实例分析 #

第七章 半定规划与近似算法 #

7.1 半定规划基础 #

7.1.1 半定规划问题形式化 #

7.1.2 半定规划对偶理论 #

7.1.3 半定规划求解算法 #

7.2 基于半定规划的近似算法 #

7.2.1 最大割问题的半定规划近似 #

7.2.2 图着色问题的半定规划近似 #

7.2.3 约束满足问题的半定规划近似 #

7.3 随机超平面舍入 #

7.3.1 超平面舍入技术 #

7.3.2 近似比分析 #

7.3.3 改进的舍入策略 #

第八章 流算法与次线性算法 #

8.1 数据流模型 #

8.1.1 流算法基本模型 #

8.1.2 空间复杂度分析 #

8.1.3 流算法设计技术 #

8.2 经典流算法 #

8.2.1 频繁项估计 #

8.2.2 基数估计 #

8.2.3 范数估计 #

8.3 次线性时间算法 #

8.3.1 属性测试 #

8.3.2 子线性时间近似 #

8.3.3 采样技术 #

第九章 分布式近似算法 #

9.1 分布式计算模型 #

9.1.1 消息传递模型 #

9.1.2 同步与异步模型 #

9.1.3 通信复杂度分析 #

9.2 图问题的分布式近似 #

9.2.1 分布式最大独立集 #

9.2.2 分布式图着色 #

9.2.3 分布式最小生成树 #

9.3 局部算法 #

9.3.1 局部算法模型 #

9.3.2 局部可检查性 #

9.3.3 局部算法的近似保证 #

第十章 近似算法前沿与发展 #

10.1 硬度的近似 #

10.1.1 唯一游戏猜想 #

10.1.2 不可近似性结果 #

10.1.3 条件硬度的应用 #

10.2 机器学习中的近似算法 #

10.2.1 近似优化在机器学习中的应用 #

10.2.2 大规模优化的近似方法 #

10.2.3 深度学习中的近似技术 #

10.3 新兴应用领域 #

10.3.1 量子近似算法 #

10.3.2 生物信息学中的近似算法 #

10.3.3 网络科学中的近似方法 #