算法与数据结构 / NP 完全性 · 判定、归约与近似 / 近似算法与不可近似性 待审核 3 / 3
2-approximation · Christofides · FPTAS

近似算法与不可近似性

归约：把难度搬到新问题上 交出的是一条坏消息：手上这个问题至少和 SAT 一样难。坏消息之后有三条路可走。缩小输入规模，靠剪枝把指数搜索压到可忍受，见 精确解：回溯、剪枝与对称 与 分支限界的拆解；找结构性假设，让问题落回 P，见 建模与归约：把问题翻译成网络流；或者放弃最优，换一个带证明的次优解。本页走第三条。

1 · approximation ratio

放弃最优的第一件事是把「差多少」说清楚，否则算法交出的东西与随便猜没有区别。

定义 1.1（approximation ratio） 对最小化问题，算法 AA 的 approximation ratio 是 ρ\rho，若对每个实例 II 都有 A(I)≤ρ⋅OPT(I)A(I) \le \rho \cdot \mathrm{OPT}(I)。最大化问题同理，不等号反向。ρ\rho 必须对所有实例成立，不是平均情形的说法。

难点在 OPT(I)\mathrm{OPT}(I)：它本身是那个算不出来的东西。近似算法的证明因此都绕同一个弯——找一个能在多项式时间内算出来的量 LL，先证 L≤OPTL \le \mathrm{OPT}，再证算法的输出不超过 ρL\rho L。整套论证从头到尾不需要知道 OPT\mathrm{OPT} 是多少。§2 与 §3 各是这个套路的一个实例，LL 分别取 maximal matching 的大小与 MST 的权重。

2 · vertex cover 的 2-approximation

vertex cover 的判定版在 归约：把难度搬到新问题上 §4 里已经拿到 NP-complete 的身份。它的近似算法短到可以整个写进一句话：随便找一个 maximal matching，把匹配边的所有端点交出去。

定理 2.1 设 MM 是图 GG 的任意一个 maximal matching，CC 是 MM 中各边端点的并集。则 CC 是 GG 的 vertex cover，且 ∣C∣≤2 OPT|C| \le 2\,\mathrm{OPT}。

证明 分三步。

其一，CC 盖住每条边。反设边 e=(u,v)e = (u, v) 未被盖住，即 u∉Cu \notin C 且 v∉Cv \notin C。两个端点都不在 CC 里，意味着它们都没有被 MM 匹配，那么 MM 加上 ee 仍是一个匹配，与 MM 的极大性矛盾。

其二，∣M∣≤OPT|M| \le \mathrm{OPT}。MM 中的边两两不共端点。任何 vertex cover 都必须盖住 MM 的每一条边，即为每条边至少贡献一个端点；这些端点分属不同的边，两两不同，故任何 vertex cover 至少有 ∣M∣|M| 个点。

其三，∣C∣=2∣M∣|C| = 2|M|，因为每条匹配边贡献两个互不相同的端点。合起来 ∣C∣=2∣M∣≤2 OPT|C| = 2|M| \le 2\,\mathrm{OPT}。∎

整个证明没有用到 MM 是怎么找出来的：任意扫边顺序、任意贪心策略，只要结果极大，界就成立。这也是它在工程上好用的原因，一趟线性扫描即可。

图 2-1 · maximal matching 的逐边扫描，绿色是被收下的匹配边，蓝色点是最终交出的 cover。可换图观察上界是否被取到，结论条对照暴力求出的最优解给出实际比值。

上界 22 什么时候取到，在三张样例图上实测过：六点链交出 66 个点而最优是 33，3×33 \times 3 网格交出 88 个而最优是 44，两处都正好翻倍；星形加一条尾巴那张图交出 44 个、最优 33 个，比值只有 1.331.33。翻倍并不罕见，任何 Kn,nK_{n,n} 都能把它逼满——maximal matching 会把两侧各 nn 个点全部选进来，而单侧的 nn 个点就够了。

警示 · 「取度数最大的点，删掉它的边，重复」这个更聪明的贪心，approximation ratio 不是常数而是 Θ(log⁡n)\Theta(\log n)。看上去更精明的策略拿不到更好的界，是近似算法里的常态：界来自能证明的下界，不来自直觉上的进取心。

3 · metric TSP 与 Christofides

TSP 要求走遍所有点再回到起点，总长最短。一般形式连常数比都拿不到（见 §5），但加上一条假设就不同了：距离满足 triangle inequality，即绕路不会比直连更短。这个版本叫 metric TSP，欧氏平面上的点集自动满足。

下界取 MST 的权重。把最优 tour 拿掉任意一条边，剩下的是一条经过所有点的路径，也是一棵生成树，所以 MST 的权重不超过最优 tour 的长度。链接的 MST 算法见 最小生成树：Prim 与 Kruskal。

double-tree 由此得到 22：把 MST 的每条边走两遍，得到一条闭合走法，长度是 MST 权重的两倍，不超过最优 tour 的两倍；这条走法会重复经过某些点，按首次出现的顺序抄近路跳过重复，triangle inequality 保证跳过不会变长。

Christofides 的改进在于不翻倍。MST 里度数为奇数的点必成偶数个（度数之和等于边数的两倍），只有它们妨碍一笔画。在这些奇度点上求一个最小权完美匹配，加进 MST，所有点的度数就都成了偶数，一笔画走完再抄近路。匹配的权重不超过 OPT/2\mathrm{OPT}/2：最优 tour 在这些奇度点上诱导出的回路可以拆成两个不相交的完美匹配，二者之和不超过最优 tour，较小的那个不超过一半。合起来是 OPT+OPT/2\mathrm{OPT} + \mathrm{OPT}/2，比值 3/23/2。

图 3-1 · 两种构造的分阶段展开：MST、（Christofides 另有奇度点与最小权完美匹配）、走法、抄近路。可换点集与算法，长度条同时给出最优 tour 与 MST 下界作对照。

三个点集上的实测比值：double-tree 分别是 1.2121.212、1.1391.139、1.1971.197，Christofides 是 1.0001.000、1.0471.047、1.1051.105。保证的 22 与 3/23/2 在这三个点集上都留着相当大的余量；余量不是保证，构造性的坏实例能把两个界分别逼近。

写这一页时踩到一个坑，值得记下来：为了让读数好看，一度把距离乘 100100 取整。整数化之后 triangle inequality 立刻在双簇点集上失效——两个簇内部的短距离各自向下取整，跨簇的长距离向上取整，d(i,j)>d(i,k)+d(k,j)d(i, j) > d(i, k) + d(k, j) 就出现了。抄近路那一步的论证全靠这条不等式，一旦失效，22 与 3/23/2 两个界都不再有依据。代码里的距离因此一律保留浮点原值，测试里也留了一条断言看住整数化会破坏它。

4 · 近似能力的层级

常数比之上还有更细的分层：有些问题的 approximation ratio 可以要多好有多好，代价是运行时间随精度膨胀。

定义 4.1（PTAS 与 FPTAS） 问题有 PTAS，若对每个固定的 ε>0\varepsilon > 0 都存在 (1+ε)(1 + \varepsilon)-approximation 算法，其运行时间对输入规模 nn 是多项式（允许对 1/ε1/\varepsilon 任意膨胀，如 n1/εn^{1/\varepsilon}）。若运行时间对 nn 与 1/ε1/\varepsilon 同时是多项式，则称 FPTAS。

三层的包含关系是 FPTAS 收得最紧，PTAS 次之，APX（存在某个常数比近似算法的问题）最宽。vertex cover 与 metric TSP 都在 APX 里；除非 P == NP，它们都没有 PTAS。

subset sum 有 FPTAS，做法是给可达和的列表定期瘦身。逐个把数并进来，列表长度每次翻倍；随即扫一遍，相对差不超过 δ=ε/2n\delta = \varepsilon / 2n 的相邻两项只留前一个。每次修剪至多引入 1+δ1 + \delta 的相对误差，nn 轮累积不超过 (1+δ)n≤1+ε(1 + \delta)^n \le 1 + \varepsilon；而列表长度被压到 O(log⁡(target)/δ)O(\log(\text{target}) / \delta)，对 nn 与 1/ε1/\varepsilon 都是多项式。站内的精确解法见 多重子集和。

图 4-1 · 可达和列表的逐轮膨胀与修剪，红色是被 δ\delta 剪掉的项。可拖动 ε\varepsilon 观察列表峰值长度与最终误差如何此消彼长。

样例上的读数：八个数、上限 10001000，不修剪时可达和列表最长 6666 项；取 ε=0.3\varepsilon = 0.3 后峰值压到 1212 项，近似解 910910、精确最优 920920，实际误差 1.1%1.1\%，远好于允许的 30%30\%。这个差距是 FPTAS 的常态：误差界按最坏情形层层放大，实际很少用满。

5 · 拿不到常数比的那些问题

不是每个 NP-hard 问题都能落进 APX。一般 TSP（不假设 triangle inequality）除非 P == NP，否则不存在任何常数比的近似算法。

论证只用一次归约。设存在一个 α\alpha-approximation 算法。给一张要判定 Hamiltonian cycle 的图 GG，构造一个完全图：GG 中有边的点对距离取 11，没有边的取 αn+1\alpha n + 1，nn 是点数。若 GG 有 Hamiltonian cycle，最优 tour 长度恰是 nn，近似算法的输出不超过 αn\alpha n，只能全走原有的边；若没有，任何 tour 至少用一条长边，长度超过 αn\alpha n。那个近似算法的输出落在哪一侧，就直接判定了 Hamiltonian cycle，而它是 NP-complete 的。站内对该问题的展开见 Hamilton 路径与回路。

更精细的不可近似结果不靠这种直接构造，而靠 PCP 定理：Håstad 证明除非 P == NP，MAX-3SAT 的 approximation ratio 不可能优于 7/87/8 [3]，而随机给每个变量抛硬币就能期望满足 7/87/8 的 clause。上界与下界在同一个数字上会合，这类结果把「还能改进多少」这个问题彻底关上。

对工程的含义很直接：看到 NP-hard 不必立刻放弃，先问它在哪一层。落在 FPTAS 那层，精度是可以买的；落在 APX 那层，常数比拿得到、再往下就得付指数代价；落在最外层，任何「保证不超过最优多少倍」的承诺都是假的，只能退回启发式与实测。

6 · 参考文献

  1. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem (Report 388). Graduate School of Industrial Administration, Carnegie Mellon University.
  2. Ibarra, O. H., & Kim, C. E. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4), 463–468.
  3. Håstad, J. (2001). Some optimal inapproximability results. Journal of the ACM, 48(4), 798–859.
  4. Vazirani, V. V. (2001). Approximation Algorithms. Springer.