近似算法

引用

Vazirani, V. V. (2001). Approximation Algorithms (1st ed.). Springer. (Corrected second printing 2003; softcover reprint 2010.)

章节概要

全书共三十章，分为三部分，另有两个附录。几乎每一章都围绕一个问题展开，章末附有习题和注记，正文篇幅很短。

第1章：Introduction（引言）

提出近似保证的基本思想，并以顶点覆盖为例说明如何通过为最优值（OPT）找下界来完成分析。本章还讨论近似保证能否改进，并引入“良刻画问题”（well-characterized problems）与极小—极大关系。

第一部分，第2–4章：集合覆盖；Steiner 树与 TSP；多路割与 k-割

集合覆盖用贪心算法和分层（layering）两种方法处理，并应用到最短超串问题。随后是 Steiner 树与度量 TSP，包括简单的 2 倍算法以及将 TSP 改进到 3/2 的算法，再之后是多路割与最小 k-割问题。

第一部分，第5–7章：k-中心；反馈顶点集；最短超串

k-中心问题用参数化剪枝处理，并包含加权版本。反馈顶点集使用圈数加权图与分层。最短超串先给出 4 倍算法，再改进到 3 倍。

第一部分，第8–11章：背包；装箱；最小完工时间调度；欧氏 TSP

这几章围绕近似方案展开。背包问题包括伪多项式时间算法、FPTAS，并讨论强 NP 困难性。装箱得到渐近 PTAS，完工时间调度得到 2 倍算法和 PTAS，欧氏 TSP 则先给出算法，再证明其正确性。

第二部分，第12–15章：LP 对偶与集合覆盖

第12章介绍 LP 对偶、极小—极大关系、本部分的两种设计技术（舍入与原始—对偶模式）以及整数性间隙。第13–15章三次回到集合覆盖：用对偶拟合分析贪心算法、舍入（简单舍入与随机舍入，并涉及顶点覆盖的半整数性），以及原始—对偶模式。

第二部分，第16–21章：最大可满足性到最稀疏割

最大可满足性通过去随机化和 LP 舍入处理，得到 3/4 倍算法。不相关并行机调度使用极点解的性质。第18–21章依次讲树上的多割、多路割、一般图上的多割和最稀疏割，其中最稀疏割借助度量、割填充和低失真嵌入。

第二部分，第22–26章：Steiner 森林到半定规划

Steiner 森林使用带同步的原始—对偶模式，Steiner 网络使用迭代舍入。随后是设施选址和 k-中位问题，后者包含一种拉格朗日松弛技术。第26章介绍半定规划，并对 MAX-2SAT 应用随机舍入。

第三部分，第27–30章：其他主题

格中的最短向量（第27章）、两个计数问题（DNF 解的计数与网络可靠性，第28章）、以 PCP 定理为基础的近似难度，并以集合覆盖的难度结果为高潮（第29章），以及一份开放问题清单（第30章）。附录 A 为算法设计者概述复杂性理论，附录 B 介绍基本概率论。

核心概念

第1–11章

• 为 OPT 找下界：近似比的证明，是把算法输出与一个容易计算的最优值下界相比较。
• 分层与参数化剪枝：用于集合覆盖、反馈顶点集和 k-中心的两种组合技术。
• PTAS 与 FPTAS：保证可以任意接近 1 的近似方案；背包一章讨论了 FPTAS 何时才可能存在。

第12–26章

• LP 对偶与整数性间隙：连接线性规划与其对偶的定理，以及限制基于某个松弛的任何分析的比值。
• 对偶拟合、舍入、原始—对偶模式：把 LP 松弛变成带保证的算法的三种方式。
• 迭代舍入与半定松弛：用于 Steiner 网络和 MAX-2SAT 的更复杂的舍入方法。

第27–30章

• 间隙归约与 PCP 定理：近似难度结果背后的工具。
• 近似计数：近似解的个数，而不是对解做优化。

评析

优点

• 章节短小，每章围绕一个问题。 前言说明各章力求简短，往往只给出核心结果，推广内容放入习题。因此很适合一次读一章。
• 习题与提示。 几乎每章都有习题和注记，前言还说明部分习题附有提示。
• 技术脉络体现在结构中。 第二部分按技术组织；集合覆盖依次用贪心、对偶拟合、舍入和原始—对偶方法重访，并在第29章给出与之匹配的难度结果。把同一个问题放在多种视角下观察，对教学很有帮助。
• 背景知识自足。 附录涵盖复杂性理论与概率，LP、半定规划和格分别在第12、26、27章引入。
• 书评者的评价。 Mark Jerrum（Mathematical Reviews，2002）称其可能是第一本对该主题作广泛而系统覆盖的教材，并称赞其习题丰富。Viggo Kann（Zentralblatt MATH，2003）认为书中的结果往往比原始论文更容易理解；Csanád Imreh（Acta Scientiarum Mathematicarum，2002）认为它既可用于研究生课程，也适合研究人员。

局限

• 2001 年的快照。 作者写明本书呈现的是撰写时的理论状况，并预期这一图景会改变；开放问题清单也被描述为围绕当时的热点问题。
• 第一部分有意保持多样。 前言承认，由于没有严格归类技术，组合算法部分可能显得不够连贯。想要按技术讲授的读者会觉得第二部分更有系统性。
• 部分证明需要接受。 第29章假定 PCP 定理成立，前言说明该定理目前没有简单证明；书中也不涉及用于计数的马尔可夫链蒙特卡罗方法。
• 内容超出一门课。 前言说明内容量超过一学期课程的两倍，因此读者需要自己选择路线。

在课程中的定位

在本课程书单中，Vazirani 是一本专门性的教材。Introduction to Algorithms（Cormen、Leiserson、Rivest 和 Stein）是通用参考书；其第35章是近似算法一章，第34章讲 NP 完全性，而这正是 Vazirani 所假定的基础。Skiena 的 The Algorithm Design Manual 是识别并解决算法问题的实用指南，近似算法是其中的方法之一。Roughgarden 的 Algorithms Illuminated 与 Cormen 的 Algorithms Unlocked 是更平缓的算法入门读物，适合尚未准备好读研究生教材的读者。

最接近的对照是 Williamson 和 Shmoys 的 The Design of Approximation Algorithms，同一主题的研究生教材，其页面介绍说内容从贪心方法一直到半定规划，并讨论理论极限。两本书覆盖的核心内容相近；Vazirani 的特点是以问题为中心的短章和三部分结构，因此两书适合对照阅读。Mitzenmacher 等人的 Probability and Computing 是第14、16、26章中随机舍入的有益补充。

如何使用本书

本书面向高年级本科生和研究生。前言指出，修过本科算法课并学过 NP 完全性理论，对大多数章节已足够；附录 A 和 B 可以帮助复习复杂性与概率。

较合理的第一遍路线是：先读第1章，再读第一部分的第2、3、5和8–10章（前言说明各部分章节大致按难度递增排列）。接着读第12–15章，它们在同一个熟悉的问题上引入 LP 对偶和三种 LP 技术，然后读第16、17和24章。第18–23、25、26章可作为可选的第二遍，适合想学习割、网络设计、聚类和半定方法的读者。想了解难度一面的读者，可在读过附录 A 后阅读第29章。对于一般的算法课程，前言只推荐把第一、二部分的前几章作为补充读物。

请做习题：推广和相关结果都放在习题里，章末注记则给出进一步阅读的参考文献。