第 35 章近似算法 (Approximation Algorithms)

核心结论

近似比定义：对优化问题，最大化时 \(C^*/C\)、最小化时 \(C/C^*\) 的最大值 ≤ \(\rho(n)\)；1-近似 = 最优解，\(\rho\) 越大近似越差。
顶点覆盖 2-近似：贪心选边、加入两端点并删除所有覆盖的边——得到的覆盖 ≤ 2 × 最优（Theorem 35.1）；核心：选出的边集 A 是极大匹配，作为下界。
TSP 与三角不等式：满足三角不等式时，最小生成树 → 前序遍历给出 2-近似（Theorem 35.2）；无三角不等式时除非 P = NP，否则无常数近似（Theorem 35.3）。
集合覆盖 greedy = \(H(n)\) 近似：贪心选覆盖最多元素的集合，Theorem 35.4 证明大小 ≤ \(H(\max\lvert S \rvert)\) · 最优；其中 \(H(d)\) 为第 d 个调和数。
MAX-3-CNF 可满足性 8/7 近似：独立随机赋真值给变量，期望满足 7/8 子句 → 8/7-近似（Theorem 35.6）。
加权顶点覆盖 2-近似（LP）：用线性规划松弛得到分数解，按阈值 1/2 取整为整数解（Theorem 35.7）；LP 松弛给最优值的下界。
子集和 FPTAS：精确算法指数时间；APPROX-SUBSET-SUM 用「修剪」列表保持多项式大小 + (1+ε) 近似。

本章主旨

面对 NP 完全问题有三条出路：小数据指数算法、特殊情形多项式算法、近似算法。本章给出 5 个具体案例：顶点覆盖（2-近似）、TSP（满足/不满足三角不等式的对比）、集合覆盖（贪心 = \(H\) 近似）、MAX-3-CNF（随机化 8/7 近似）、加权顶点覆盖（LP 松弛 2-近似）；最后给出子集和的完全多项式时间近似方案 (FPTAS)。证明近似比的核心方法是「构造解 + 与最优下界比较」——贪心选择提供下界（极大匹配、最小生成树、覆盖数），构造的解与下界之比即为近似比。

一、核心概念

本章围绕 5 个核心概念展开：先建立近似比的定义与术语，再分别给出贪心、LP 松弛、随机化、FPTAS 四种技术路线。

概念	定义 + 重要性	实现提示
近似比 (Approximation Ratio)	对输入大小 n，算法解 cost \(C\) vs 最优 \(C^\)，满足 \(\max(C/C^, C^*/C) \leq \rho(n)\)；\(\rho = 1\) 即最优。	§35 开头；式 35.1 定义；最小化与最大化形式略有不同。
顶点覆盖 2-近似 (APPROX-VERTEX-COVER)	贪心选边 (u, v)，加 u、v 到 C，删所有 u/v 邻边；返回 C 必 ≤ 2 倍最优。	§35.1；Theorem 35.1；核心：选出的边集 A 是极大匹配，\(\lvert A \rvert \leq \lvert C^* \rvert\)，故 \(\lvert C \rvert = 2\lvert A \rvert \leq 2\lvert C^* \rvert\)。
TSP 与三角不等式 (APPROX-TSP-TOUR)	若 cost 满足三角不等式：先求 MST，再前序遍历 MST 得哈密尔顿圈 \(H\)；\(c(H) \leq 2 \cdot c(H^*)\)。	§35.2.1；Theorem 35.2；无三角不等式时无常数近似除非 P = NP（Theorem 35.3）。
集合覆盖贪心 (GREEDY-SET-COVER)	每步选覆盖最多未覆盖元素的集合；返回覆盖大小 \(\lvert C \rvert \leq H(\max\lvert S \rvert) \cdot \lvert C^* \rvert\)，\(H(d)\) 为调和数。	§35.3；Theorem 35.4；Corollary 35.5：\(\lvert C \rvert \leq (\ln\lvert X \rvert + 1)\lvert C^* \rvert\)。
加权顶点覆盖 LP 松弛 (APPROX-MIN-WEIGHT-VC)	用 LP 松弛求分数解 \(x^*(v)\)；按阈值 1/2 取整得整数解；返回覆盖权重 ≤ 2 × 最优。	§35.4；Theorem 35.7；LP 最优值为权重下界；rounding 给出 2-近似。
FPTAS (APPROX-SUBSET-SUM)	子集和优化：精确指数时间；用「修剪」参数 \(\delta = \varepsilon/2n\) 保持列表多项式大小，返回 (1+ε)-近似。	§35.5；Theorem 35.8；FPTAS = 多项式时间且对 ε 取多项式依赖。

概念

定义 + 重要性

实现提示

近似比 (Approximation Ratio)

对输入大小 n，算法解 cost \(C\) vs 最优 \(C^*\)，满足 \(\max(C/C^*, C^*/C) \leq \rho(n)\)；\(\rho = 1\) 即最优。

§35 开头；式 35.1 定义；最小化与最大化形式略有不同。

顶点覆盖 2-近似 (APPROX-VERTEX-COVER)

贪心选边 (u, v)，加 u、v 到 C，删所有 u/v 邻边；返回 C 必 ≤ 2 倍最优。

§35.1；Theorem 35.1；核心：选出的边集 A 是极大匹配，\(\lvert A \rvert \leq \lvert C^* \rvert\)，故 \(\lvert C \rvert = 2\lvert A \rvert \leq 2\lvert C^* \rvert\)。

TSP 与三角不等式 (APPROX-TSP-TOUR)

若 cost 满足三角不等式：先求 MST，再前序遍历 MST 得哈密尔顿圈 \(H\)；\(c(H) \leq 2 \cdot c(H^*)\)。

§35.2.1；Theorem 35.2；无三角不等式时无常数近似除非 P = NP（Theorem 35.3）。

集合覆盖贪心 (GREEDY-SET-COVER)

每步选覆盖最多未覆盖元素的集合；返回覆盖大小 \(\lvert C \rvert \leq H(\max\lvert S \rvert) \cdot \lvert C^* \rvert\)，\(H(d)\) 为调和数。

§35.3；Theorem 35.4；Corollary 35.5：\(\lvert C \rvert \leq (\ln\lvert X \rvert + 1)\lvert C^* \rvert\)。

加权顶点覆盖 LP 松弛 (APPROX-MIN-WEIGHT-VC)

用 LP 松弛求分数解 \(x^*(v)\)；按阈值 1/2 取整得整数解；返回覆盖权重 ≤ 2 × 最优。

§35.4；Theorem 35.7；LP 最优值为权重下界；rounding 给出 2-近似。

FPTAS (APPROX-SUBSET-SUM)

子集和优化：精确指数时间；用「修剪」参数 \(\delta = \varepsilon/2n\) 保持列表多项式大小，返回 (1+ε)-近似。

§35.5；Theorem 35.8；FPTAS = 多项式时间且对 ε 取多项式依赖。

二、详细笔记

2.1 顶点覆盖 2-近似 (APPROX-VERTEX-COVER)

What：贪心选边 (u, v) 加入 C，删除所有与 u 或 v 关联的边，直到无剩余边；返回 C 是一个顶点覆盖且 \(\lvert C \rvert \leq 2\lvert C^* \rvert\)。

Why：VERTEX-COVER 是 NPC 优化问题（决策版 NP 完全）；这个 2-近似是近似算法的入门案例——证明思路可推广到许多其他问题。

How：

步骤	操作
1	初始化 C = ∅, E' = E
2	while E' ≠ ∅: 任取边 (u, v) ∈ E'
3	C ← C ∪ {u, v}
4	从 E' 删除所有与 u 或 v 关联的边
5	返回 C

时间 \(O(V + E)\)（邻接表实现）。

证明思路（Theorem 35.1）： * A = 第 2 行选出的边集；A 是极大匹配（无两共享端点） * 每个顶点覆盖必覆盖 A 中每条边至少一个端点 → \(\lvert C^* \rvert \geq \lvert A \rvert\) * 算法选出 \(\lvert C \rvert = 2\lvert A \rvert\) 个顶点 * 故 \(\lvert C \rvert = 2\lvert A \rvert \leq 2\lvert C^* \rvert\)

When：处理顶点覆盖问题的默认近似算法；当需要更紧近似时可考虑 LP 松弛的 2-近似（理论上同样 2 倍但实践中通常更小）。

Example：Figure 35.1 的 7 顶点图：算法返回 6 个顶点 (b, c, d, e, f, g)；最优覆盖是 {b, d, e} 仅 3 个顶点——近似比为 2。

2.2 TSP 与三角不等式

What：三角不等式是 TSP 是否可近似 2 倍的分水岭——有 / 无两种情形给出截然不同的结论。

满足三角不等式时：MST + 前序遍历给出 2-近似（Theorem 35.2）
无三角不等式时：除非 P = NP 否则无常数近似（Theorem 35.3）

Why：TSP 是 NPC；但现实距离天然满足三角不等式（地理路径、欧氏距离）——这一结构性质使近似成为可能。无三角不等式时问题「本质上更难」（可归约 Hamilton 圈）。

How — APPROX-TSP-TOUR：

步骤	操作
1	选根节点 r ∈ V
2	用 MST-PRIM 求最小生成树 T（从 r 开始）
3	对 T 做前序遍历（preorder walk），得顶点列表 H
4	返回 H 作为哈密尔顿圈

时间 \(\Theta(V^2)\)（MST-PRIM 实现）。

证明（Theorem 35.2）： * 从最优圈 H* 删一条边得生成树，故 \(c(T) \leq c(H^*)\) * 完整遍历 T 走每条边两次，故 \(c(\text{full walk}) = 2c(T)\) * 由三角不等式，「跳过」中间顶点不减 cost，得 \(c(H) \leq c(\text{full walk})\) * 合并：\(c(H) \leq 2c(T) \leq 2c(H^*)\)

无三角不等式的反证（Theorem 35.3）： * 假设存在 ρ-近似算法 A * 给定 Hamilton 圈实例 G，构造完全图 G'：G 中边 cost 1，其他 cost ρ|V|+1 * G 有 Hamilton 圈 ⇔ G' 有 cost |V| 的 TSP 圈 * A 的输出 cost ≤ ρ|V| 当且仅当 G 有 Hamilton 圈 * 故 A 可解 Hamilton 圈，与 P ≠ NP 矛盾

When：现实路径规划问题（满足三角不等式时）；不适用于任意抽象 cost 函数。

Example：8 个平面点，欧氏距离：APPROX-TSP-TOUR 返回约 19.07；最优约 14.72——近似比约 1.30 < 2（实际通常更好）。

2.3 集合覆盖贪心 (GREEDY-SET-COVER)

What：每步选「覆盖最多未覆盖元素」的集合加入 C，直到所有元素被覆盖；Theorem 35.4 证明 \(\lvert C \rvert \leq H(\max\lvert S \rvert) \cdot \lvert C^* \rvert\)。

Why：集合覆盖的决策版是 NP 完全（可归约自顶点覆盖）；贪心算法简单实用，近似比以调和数增长——对于 \(\max\lvert S \rvert\) 较小的情形（如 ≤ 10），近似比 < 3，非常实用。

How：

步骤	操作
1	U ← X, C ← ∅
2	while U ≠ ∅: 选 S ∈ F 最大化
S ∩ U
3	U ← U \ S
4	C ← C ∪ {S}
5	返回 C

时间 \(O(\lvert X \rvert \cdot \lvert F \rvert \cdot \min(\lvert X \rvert, \lvert F \rvert))\)（简单实现）；练习 35.3-3 给出 \(O(\sum_{S \in F} \lvert S \rvert)\) 实现。

证明（Theorem 35.4）：分配成本——选 Si 时把 1 单位成本均分给 Si 首次覆盖的元素 \(x\)，记为 \(c_x\)；则 \(\lvert C \rvert = \sum_x c_x\)，关键不等式（式 35.12）对任意 \(S \in F\)，\(\sum_{x \in S} c_x \leq H(\lvert S \rvert)\)；结合 \(C^*\) 覆盖 X，得 \(\lvert C \rvert \leq \lvert C^* \rvert \cdot H(\max\lvert S \rvert)\)。

Corollary 35.5：因 \(H(d) \leq \ln d + 1\)，故 \(\lvert C \rvert \leq (\ln\lvert X \rvert + 1)\lvert C^* \rvert\)。

When：所有「覆盖」类问题——技能分配、设备选址、文档摘要等；当 \(\max\lvert S \rvert\) 很小时特别有效。

Example：X = 12 个元素，F = 6 个子集；最优覆盖大小 3；贪心返回大小 4（Figure 35.3）；近似比 4/3 < H(6) ≈ 2.45。

2.4 随机化与线性规划方法

What：本节给出两种通用近似框架——随机化与线性规划松弛。

MAX-3-CNF：独立随机赋每个变量 0/1 → 期望满足 7/8 子句（8/7-近似，Theorem 35.6）
加权顶点覆盖：LP 松弛 + 阈值取整 → 2-近似（Theorem 35.7）

Why：随机化方法用极简算法获得保证期望；LP 松弛给整数优化的下界，结合 rounding 给近似解——两种方法都是「通用框架」，适用面广。

How — MAX-3-CNF（Theorem 35.6）：

每子句独立被满足概率 = 1 - (1/2)^3 = 7/8；设 Y = 满足子句数，E[Y] = 7m/8；m ≤ C*，故 E[C/C*] ≤ m/(7m/8) = 8/7。

How — 加权顶点覆盖 LP 松弛（Theorem 35.7）：

步骤	操作
LP	min \(\sum w(v) x(v)\) s.t. \(x(u) + x(v) \geq 1\) ∀(u,v) ∈ E, \(0 \leq x(v) \leq 1\)
解	求最优分数解 \(x^*(v)\)
取整	if \(x^*(v) \geq 1/2\): 加 v 到 C
返回	C

步骤

操作

min \(\sum w(v) x(v)\) s.t. \(x(u) + x(v) \geq 1\) ∀(u,v) ∈ E, \(0 \leq x(v) \leq 1\)

解

求最优分数解 \(x^*(v)\)

取整

if \(x^*(v) \geq 1/2\): 加 v 到 C

证明：\(z^* \leq w(C^*)\)（LP 最优 ≤ 整数最优）；每边 (u,v) 至少一个端点 \(x^* \geq 1/2\)，故 C 是覆盖；每加入 v 满足 \(w(v) \leq 2 w(v) x^*(v)\)，故 \(w(C) \leq 2 z^* \leq 2 w(C^*)\)。

When：两种框架适用场景不同。

随机化：当问题结构允许独立随机化、且解可被快速验证（设置变量后容易验证子句是否满足）
LP 松弛：当问题可自然表示为 0-1 整数规划（如覆盖、调度、网络设计）

Example：MAX-3-CNF：任意实例（每个子句恰 3 个不同 literal，无变量和否定同现）；加权顶点覆盖：任意正权图。

2.5 子集和 FPTAS

What：APPROX-SUBSET-SUM 输入 S, t, ε；输出和 ≤ t 的子集的最大和值，结果在 [最优, (1+ε)最优] 内；运行时间多项式于 1/ε 与 n。

Why：子集和决策版 NP 完全；优化版通常需要 FPTAS（全多项式时间近似方案）——在 worst-case 不可解但可任意精度近似。

How — APPROX-SUBSET-SUM：

步骤	操作
1	L₀ ← ⟨0⟩
2	for i = 1 to n: Li ← MERGE-LISTS(L_{i-1}, L_{i-1} + xᵢ)
3	Li ← TRIM(Li, ε/2n)
4	删除 Li 中 > t 的元素
5	返回 Ln 最大元素

TRIM 移除「相近」元素——若删除 y 后剩余 z 满足 \(y/(1+δ) \leq z \leq y\)，则 z 代理 y。

时间：MERGE-LISTS 单次 \(O(\lvert Li-1 \rvert)\)；TRIM 线性；每步总线性 → 总时间 \(O(n^2 / ε)\)，对 n 和 1/ε 均多项式。

证明思路（Theorem 35.8）：TRIM 后每个被删除元素可被保留元素以 (1+δ) 因子近似，故 TRIM 不显著改变可达和；递归得最终和 ≥ 最优 / (1+ε)^n ≥ 最优 / (1+ε)（当 ε 小时近似 = e^{nε/(2n)} = e^{ε/2} ≈ 1 + ε/2，再合并后半部分得 1+ε）。

When：所有 NP 完全的数值优化问题——子集和、背包变种、资源分配等；当要求任意精度近似时首选 FPTAS。

Example：S = {1, 4, 5}, t = 8：精确最优 = 8（1+4+…不对，是 1+4+…无解 8），实际最优 = 5（4+…不对），最大 ≤ 8 = 4+…无 8 是 1+4+…无；ε = 0.5 时 TRIM 参数 δ = 0.125。

三、关键图表

核心公式对照表

公式编号

内容

式 35.1

近似比：\(\max(C/C^*, C^*/C) \leq \rho(n)\)

顶点覆盖下界

极大匹配 A：\(\lvert A \rvert \leq \lvert C^* \rvert\)

顶点覆盖 2-近似

\(\lvert C \rvert = 2\lvert A \rvert \leq 2\lvert C^* \rvert\)

TSP 三角不等式

\(c(H) \leq c(\text{full walk}) = 2c(T) \leq 2c(H^*)\)

集合覆盖

\(\lvert C \rvert \leq \lvert C^* \rvert \cdot H(\max\lvert S \rvert)\)，\(H(d) = \sum_{i=1}^d 1/i\)

Corollary 35.5

\(\lvert C \rvert \leq (\ln\lvert X \rvert + 1)\lvert C^* \rvert\)

MAX-3-CNF 期望

E[满足子句数] = 7m/8

LP 松弛下界

\(z^*_{LP} \leq z^*_{IP}\)（最优 LP ≤ 最优 IP）

FPTAS 修剪

删除 y 若 \(\exists z \in L': y/(1+\delta) \leq z \leq y\)

四、思维导图

mindmap
  root((第 35 章 近似算法))
    近似比定义
      max比值
      1为最优
      max与min形式
    顶点覆盖
      贪心选边
      极大匹配下界
      2-近似
    TSP三角不等
      MST前序遍历
      2-近似
      无三角不可近
    集合覆盖
      贪心选最大覆盖
      调和数界
      O(lgn)近似
    随机化与LP
      MAX-3-CNF 8/7
      LP松弛取整
      加权VC 2-近似
    子集和FPTAS
      修剪参数delta
      多项式大小
      (1+eps)近似

五、重点与易错点

近似比定义对最大化与最小化问题方向不同——式 35.1 的 \(\max(C/C^*, C^*/C)\) 是统一形式；务必确认 \(C\) 与 \(C^*\) 谁是分子。
APPROX-VERTEX-COVER 的 2-近似证明关键是「极大匹配」——边集 A 是极大匹配 ⟹ \(\lvert A \rvert \leq \lvert C^* \rvert\)；很多错误证明忽略「极大」二字。
TSP 三角不等式至关重要：删除中间顶点不减 cost 是核心推理；无三角不等式时 \(\rho\lvert V \rvert+1\) 的 cost 设计利用了大数差距。
Theorem 35.3 是反证法的典范——把 Hamiltonian 圈归约到 TSP，通过 cost 差距让「假定的近似算法」成为 Hamiltonian 圈的多项式解。
GREEDY-SET-COVER 的近似比与 \(\max\lvert S \rvert\) 相关，不是 \(\lvert X \rvert\)——很多人误以为与元素总数相关。
调和数 \(H(d) \approx \ln d + \gamma\)，\(\gamma ≈ 0.577\)；当 \(d\) 小时（如 3），\(H(3) = 1 + 1/2 + 1/3 = 11/6 ≈ 1.83\)，近似非常好。
MAX-3-CNF 8/7 近似要求每个子句恰 3 个不同 literal 且无变量和否定同时出现（练习 35.4-1 推广）；不满足时概率分析改变。
LP 松弛的核心价值是「给整数最优下界」——任何可行分数解的值 ≤ 整数最优；这是 rounding 近似证明的关键。
加权顶点覆盖 LP rounding 阈值 1/2 的选择：保证每边至少一个端点被选（覆盖性）+ 每顶点贡献 ≤ 2 倍 LP 值（2-近似）。
FPTAS 与 PTAS 的区别：FPTAS 运行时间多项式依赖于 1/ε；PTAS 仅对固定 ε 是多项式。子集和是少数有 FPTAS 的 NP-hard 问题。
TRIM 的「代理」思想是 FPTAS 的核心：保留的元素足以在 (1+δ) 误差内代表所有可达和；选择 δ = ε/2n 累积误差 ≈ 1+ε。
5 个案例展示 4 种近似技术：贪心（VC、Set Cover）、结构（TSP + 三角不等）、随机化（MAX-3-CNF）、LP 松弛（Weighted VC）、FPTAS（Subset Sum）。

第 35 章 近似算法 (Approximation Algorithms)