近似算法设计

引用

Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press. 作者提供的免费电子版：https://www.designofapproxalgs.com/download.php

章节概要

本书按算法技术而不是按问题来组织。第1章用多种技术处理同一个问题；第一部分（第1至8章）每种技术一章，作介绍；第二部分（第9至15章）按相同顺序回到各项技术，讨论要求更高的应用。第16、17章和两个附录收尾。各章以习题和指向文献的章末注记结束。

第1章：近似算法导论

说明为什么要研究近似算法，定义性能保证和近似方案，并指出有些问题根本不存在好的近似。随后用五种方式处理集合覆盖问题：线性规划的确定性舍入、对偶解的舍入、原始-对偶方法、贪心算法和随机舍入。作者在这里引入线性规划的术语。

第2章：贪心算法与局部搜索

对比贪心算法与局部搜索算法。涉及的问题有：单机带截止时间的调度、k-中心问题（并有硬度结果，说明因子小于2就意味着 P = NP）、相同并行机上的调度、度量旅行商问题（最近邻加入、双树和 Christofides 算法）、银行账户浮游额最大化、最小度生成树以及边着色。

第3章：数据舍入与动态规划

对舍入后的输入使用动态规划，得到背包问题、相同并行机调度和装箱问题的近似方案。

第4章：线性规划的确定性舍入

对分数解做确定性舍入。应用包括单机上（加权）完工时间之和的最小化、带奖励的 Steiner 树问题、无容量设施选址和装箱。有一节说明如何用椭球法在多项式时间内求解大型线性规划。

第5章：线性规划的随机抽样与随机舍入

从 MAX SAT 和 MAX CUT 的简单随机算法开始，讲解去随机化、有偏硬币和随机舍入，然后是非线性舍入和从两个解中取较优者。其他应用有带奖励的 Steiner 树、设施选址、带释放时间的单机调度、Chernoff 界和整数多商品流，以及稠密3-可着色图的着色。

第6章：半定规划的随机舍入

介绍半定规划和用随机超平面进行舍入。应用有寻找大割、近似二次规划、相关聚类和3-可着色图的着色。

第7章：原始-对偶方法

通过一系列问题所体现的原则来展开该方法：回顾集合覆盖问题、反馈顶点集、最短 s-t 路径、广义 Steiner 树问题、最小背包问题，然后是用拉格朗日松弛处理的无容量设施选址和 k-中位问题。

第8章：割与度量

通过度量和线性规划处理割问题：多路割（基于最小割的算法和线性规划舍入算法）、多割、平衡割、用树度量对度量作概率近似（以 buy-at-bulk 网络设计为应用），以及用于线性排列的扩张度量。

第9–10章：贪心与局部搜索的更多应用；数据舍入与动态规划的更多应用

第9章回到最小度生成树的局部搜索，得到与最优值相差不超过1的结果，并发展设施选址和 k-中位问题的局部搜索与贪心算法。第10章给出欧氏旅行商问题（对平面作递归划分并做动态规划）和平面图最大独立集的近似方案。

第11–12章：线性规划确定性舍入的更多应用；随机抽样与随机舍入的更多应用

第11章讲广义指派问题、最小费用度数受限生成树，以及基于基本可行解的迭代舍入与可生存网络设计。第12章用组合的随机算法再次回到设施选址，然后是单源租或买问题、Steiner 树问题，以及在稠密图中寻找大割。

第13–15章：半定规划、原始-对偶方法、割与度量的更多应用

第13章利用正态分布的性质，把半定规划的分析扩展到二次规划和3-可着色图，并加入唯一博弈。第14章给出带奖励 Steiner 树和反馈顶点集的原始-对偶2-近似算法。第15章讲低失真嵌入与最稀疏割、无关路由、割-树装箱、最小二分以及均匀最稀疏割问题；其最后一节是全书最长也最复杂的证明。

第16章：证明近似困难性的技术

对困难性证明作较简短的概述：从 NP 完全问题出发的归约、保持近似的归约，以及从概率可检验证明、标签覆盖和唯一博弈出发的归约。

第17章：开放问题

一份开放问题清单，从唯一博弈猜想开始，包括度量旅行商问题及其非对称变体。

附录 A–B：线性规划；NP 完全性

对正文用到的线性规划和复杂性背景作简要回顾。

核心概念

第1–3章：基础

• 性能保证：若多项式时间算法在每个实例上的解都在最优值的 α 倍之内，就称其为 α-近似算法。
• 近似方案（PTAS）：对任意固定的 ε 都能达到 1±ε 的一族算法。
• 局部搜索与贪心构造：通过局部最优的选择来构造或改进解。

第4–8章：线性规划、半定规划、原始-对偶与度量

• 线性规划松弛与舍入：求解整数规划的分数版本，再转化为整数解。
• 随机舍入与去随机化：随机选择按期望分析，再用条件期望方法消去随机性。
• 原始-对偶方法：在构造原始解的同时构造可行对偶解，以界定成本。
• 树度量：以对数量级的损失，用随机树逼近一般度量。

第9–17章：扩展与极限

• 迭代舍入：反复求解线性规划并固定变量，用于度数受限和可生存网络设计。
• 整性间隙：整数规划与其松弛之间的差距，限制了某个形式化所能证明的结果。
• 保持近似的归约与唯一博弈猜想：证明困难性结果的工具。

评析

优点

• 围绕技术组织。 每种技术各占一章，读者学会何时该用舍入、原始-对偶或局部搜索；书中反复回到设施选址、带奖励 Steiner 树、装箱和最大割，展示更好的工具如何改进结果。
• 通过线性规划形成统一视角。 前言说明线性规划和整数规划处于核心地位，第1章和附录 A 为计算机背景的读者补充了术语。
• 为教学而设计。 全书由多次授课的讲义发展而来，只收录足够简单、适合课堂的结果，并在每章末附习题和注记。
• 坦率面对困难性。 困难性在第1章和第2章就已出现，第16章和开放问题一章说明哪些结果无法改进。

局限

• 先修要求实实在在。 前言假定读者上过算法课，熟悉证明、基本概率，并略知 NP 完全性；半定规划还需要基础线性代数。据前言，正文中为数不多的 NP 完全性归约可以略过。
• 困难性只是概述。 作者说，仅这一主题就足以另写一本书，所以第16章很简短。
• 部分内容已显陈旧。 开放问题一章反映的是2010年的领域状况，并提到已宣布但尚未发表的结果。
• 第二部分内容密集。 第二部分不是入门性的；用前言的话说，第15章中 Arora–Rao–Vazirani 的证明是全书最长也最复杂的。

在课程中的定位

在算法课程书单中，本书是紧接在 Introduction to Algorithms 之类一般算法教材之后的研究生专题读物。Vazirani 的 Approximation Algorithms 是最接近的替代品，同样是对 NP 难问题技术的细致阐述；Williamson 和 Shmoys 按技术组织并反复回到相同的问题，并且据作者自述，对调度和半定规划着墨更多。

Mitzenmacher 和 Upfal 的 Probability and Computing 是读概率相关章节（第5、6、12、13章）时有用的参照：它深入展开了 Chernoff 界和概率方法。书单中偏应用的书，如 The Algorithm Design Manual、Algorithms Illuminated 和 Algorithms Unlocked，讲的是设计与实现，不能取代本书。

如何使用本书

本书面向刚进入近似算法领域的研究生和研究人员。初学可按顺序读第一部分：第1章在集合覆盖上给出全貌，第2、3章除算法外几乎不需要其他准备，第4、5、7章发展基于线性规划的方法。第6章需要线性代数，第8章把线性规划与度量思想结合起来。

读完第一部分某项技术后若想看到更强的结果，就读第二部分对应的章节：第9章和第11.1节是不错的起点，第16章提供困难性背景。每章至少做几道习题，并借助章末注记找到原始论文。

版本与来源

本导读依据作者网站上的免费电子版（仅电子版），该文件经剑桥大学出版社许可发布，是提交给出版社的书稿；印刷版格式不同，并有少量更正。内容基于前言、目录、各章开头、结尾章节和附录。