cover.png#近似算法

上一节讨论 NP-complete 问题时，核心结论是：很多自然优化问题如果要求最优解、多项式时间、适用于所有输入，在 \(\text{P}\neq\text{NP}\) 的假设下不可能三者兼得

近似算法 (Approximation Algorithms) 的思路是要在多项式时间内找到一个有保证的近似解

常见设计方法包括：

• 贪心
• LP 松弛与舍入
• primal-dual 方法
• 局部搜索
• 随机化
• 动态规划与缩放

---

近似比

设优化问题的最优值为 \(OPT(I)\)，算法在输入 \(I\) 上输出的解值为 \(A(I)\)

最小化问题

对最小化问题，算法的目标值越小越好。若对所有输入 \(I\) 都有：

\[ A(I)\leq \alpha\cdot OPT(I) \]

其中 \(\alpha\geq 1\)，则称算法是一个 \(\alpha\)-approximation

例如 2-近似表示：

\[ A(I)\leq 2OPT(I) \]

最大化问题

对最大化问题，算法的目标值越大越好。若对所有输入 \(I\) 都有：

\[ A(I)\geq \alpha\cdot OPT(I) \]

其中 \(0<\alpha\leq 1\)，则称算法是一个 \(\alpha\)-approximation

例如 \(1/2\)-近似表示：

\[ A(I)\geq \frac{1}{2}OPT(I) \]

也有教材把最大化问题的近似比写成：

\[ \frac{OPT(I)}{A(I)}\leq \rho \]

此时 \(\rho\geq 1\)，两种写法等价，只是约定不同

下界的重要性

近似算法分析通常不是直接知道 \(OPT\)，而是找一个容易计算或证明的界：

• 最小化问题：找 \(OPT\) 的下界 \(LB\)，证明 \(A\leq \alpha LB\leq \alpha OPT\)
• 最大化问题：找 \(OPT\) 的上界 \(UB\)，证明 \(A\geq \alpha UB\geq \alpha OPT\)

本节中很多证明都遵循这个模式

---

近似算法类别

APX

如果一个优化问题存在某个常数因子的多项式时间近似算法，则称它属于 APX

例如：

• Vertex Cover 有 2-approximation
• Metric TSP 有 3/2-approximation
• Metric \(k\)-center 有 2-approximation

PTAS

PTAS (Polynomial-Time Approximation Scheme) 是一族算法。对任意固定 \(\varepsilon>0\)，算法都能在多项式时间内得到：

• 最小化问题：\((1+\varepsilon)\)-approximation
• 最大化问题：\((1-\varepsilon)\)-approximation

但运行时间可以对 \(1/\varepsilon\) 指数依赖，例如：

\[ n^{O(1/\varepsilon)} \]

当 \(\varepsilon\) 固定时它是多项式；但如果把 \(\varepsilon\) 也作为输入，可能不再高效

FPTAS

FPTAS (Fully Polynomial-Time Approximation Scheme) 要求运行时间同时关于输入规模和 \(1/\varepsilon\) 多项式

例如：

\[ O\left(\frac{n^3}{\varepsilon}\right) \]

是 FPTAS 级别的时间复杂度。

Knapsack 有 FPTAS，这是数值型弱 NP-hard 问题中的经典结论

---

负载均衡

问题定义

输入：

• \(m\) 台相同机器
• \(n\) 个作业
• 作业 \(j\) 的处理时间为 \(t_j\)

每个作业必须连续地运行在某一台机器上，每台机器同一时间最多处理一个作业。

令 \(J(i)\) 表示分配给机器 \(i\) 的作业集合，则机器 \(i\) 的负载为：

\[ L_i=\sum_{j\in J(i)}t_j \]

makespan 定义为最大机器负载：

\[ L=\max_i L_i \]

目标是最小化 \(L\)。

即：

\[ \min \max_i \sum_{j\in J(i)}t_j \]

NP-hard 性

即使只有两台机器，负载均衡也是 NP-hard 的

可以从 Partition 归约：

• 给定整数集合 \(S=\{a_1,\ldots,a_n\}\)
• 构造 \(n\) 个作业，令 \(t_j=a_j\)
• 使用两台机器

如果存在 makespan 为 \(\frac{1}{2}\sum_j a_j\) 的调度，则原集合可以被平分；反之也成立。

---

List Scheduling

List Scheduling 是最简单的贪心算法：

按某个固定顺序考虑作业，每次把当前作业分配给当前负载最小的机器。

LIST-SCHEDULING(m, n, t)
    for i = 1 to m
        L[i] = 0
        J[i] = empty
    for j = 1 to n
        i = argmin_k L[k]
        J[i] = J[i] union {j}
        L[i] = L[i] + t[j]
    return J

若用优先队列维护当前负载最小的机器，时间复杂度为：

\[ O(n\log m) \]

两个下界

设最优 makespan 为 \(L^*\)。

第一个下界：

\[ L^*\geq \max_j t_j \]

因为最长的作业必须由某台机器完整处理。

第二个下界：

\[ L^*\geq \frac{1}{m}\sum_{j=1}^n t_j \]

因为总工作量必须由 \(m\) 台机器完成，至少有一台机器承担不小于平均值的负载。

2-近似分析

设算法得到的最大负载机器为 \(i\)，其最后被分配的作业为 \(j\)。在作业 \(j\) 分配前，机器 \(i\) 是当前负载最小的机器，所以：

\[ L_i-t_j\leq L_k \]

对所有机器 \(k\) 都成立。

对所有 \(k\) 求和并除以 \(m\)：

\[ L_i-t_j \leq \frac{1}{m}\sum_{k=1}^m L_k = \frac{1}{m}\sum_{j=1}^n t_j \leq L^* \]

又因为：

\[ t_j\leq L^* \]

所以：

\[ L_i=(L_i-t_j)+t_j\leq 2L^* \]

因此 List Scheduling 是 2-approximation。

更精细的界

由于作业 \(j\) 分配前，它所在机器负载是最小的，其他 \(m-1\) 台机器负载都至少为 \(L_i-t_j\)。因此：

\[ \sum_{\ell=1}^n t_\ell \geq (m-1)(L_i-t_j)+L_i =mL_i-(m-1)t_j \]

于是：

\[ L_i \leq \frac{1}{m}\sum_{\ell=1}^n t_\ell + \left(1-\frac{1}{m}\right)t_j \leq \left(2-\frac{1}{m}\right)L^* \]

所以 List Scheduling 实际上有：

\[ \left(2-\frac{1}{m}\right)\text{-approximation} \]

这个界在最坏情况下基本是紧的。

---

LPT 规则

LPT (Longest Processing Time first) 规则：

1. 先按处理时间降序排序
2. 再运行 List Scheduling

即：

\[ t_1\geq t_2\geq\cdots\geq t_n \]

一个简单的 \(3/2\) 分析

如果 \(n\leq m\)，每个作业可以单独放在一台机器上，调度是最优的。

若 \(n>m\)，考虑第 \(m+1\) 个作业。前 \(m+1\) 个作业都至少有 \(t_{m+1}\) 的处理时间。由于只有 \(m\) 台机器，最优调度中至少有一台机器包含其中两个作业，所以：

\[ L^*\geq 2t_{m+1} \]

对 LPT 算法的瓶颈机器，设其最后一个作业为 \(j\)。如果这个作业不是前 \(m\) 个作业，则：

\[ t_j\leq t_{m+1}\leq \frac{1}{2}L^* \]

与 List Scheduling 的分析相同：

\[ L_i-t_j\leq L^* \]

所以：

\[ L_i\leq \frac{3}{2}L^* \]

因此 LPT 至少是 \(3/2\)-approximation。

Graham 的更强结果

Graham 的经典分析给出更好的界：

\[ \frac{4}{3}-\frac{1}{3m} \]

因此 LPT 是 \(4/3\) 量级的近似算法。

这个结果常被用来说明：同一个贪心算法的近似比可能取决于分析精细程度，而不是算法本身。

---

Vertex Cover

问题定义

输入无向图 \(G=(V,E)\)，目标是找最小的点集 \(C\subseteq V\)，使得每条边至少有一个端点在 \(C\) 中。

也就是：

\[ \forall (u,v)\in E,\quad u\in C \text{ or } v\in C \]

失败的贪心

一个自然想法是：反复选择当前未覆盖边中某条边的一个端点。

如果端点选择不谨慎，这个算法可能达到 \(\Omega(\log n)\)

另一个想法是：每次选择当前覆盖最多未覆盖边的顶点

这个“最大度优先”算法也可能输出很差的解，因为它类似 Set Cover 的贪心，而 Vertex Cover 虽是 Set Cover 的特殊情形，但最大度贪心不一定给出 2-近似。

所以 Vertex Cover 的简单好算法不是“选一个端点”，而是“选一条未覆盖边的两个端点”。

---

Vertex Cover 的 2-近似

算法：

APPROX-VERTEX-COVER(G)
    C = empty
    A = empty
    E' = E[G]
    while E' is not empty
        choose an arbitrary edge (u, v) in E'
        C = C union {u, v}
        A = A union {(u, v)}
        remove from E' every edge incident to u or v
    return C

这里 \(A\) 是算法选出的边集。

为什么 \(C\) 是顶点覆盖

算法只在 \(E'\) 中还有未覆盖边时继续。每次加入 \((u,v)\) 的两个端点后，删除所有与 \(u\) 或 \(v\) 相邻的边。

当算法结束时，\(E'=\emptyset\)，说明所有边都已经被 \(C\) 覆盖。

近似比分析

算法选出的边集 \(A\) 是一个匹配：任意两条边不共享端点。

任意顶点覆盖 \(C^*\) 都必须覆盖 \(A\) 中的每一条边。由于 \(A\) 是匹配，覆盖这些边至少需要每条边选一个不同端点，所以：

\[ |C^*|\geq |A| \]

而算法每选一条边，就把两个端点加入 \(C\)，因此：

\[ |C|=2|A| \]

于是：

\[ |C|=2|A|\leq 2|C^*| \]

因此该算法是 2-approximation

匹配下界视角

这个证明的关键是：匹配大小给出了最小顶点覆盖大小的下界。

\[ \text{maximum matching size}\leq \text{minimum vertex cover size} \]

在二分图中，由 König 定理二者相等，所以二分图 Vertex Cover 可以精确求解；在一般图中，最大匹配仍然给出一个足够好的下界，从而得到 2-近似

---

Weighted Vertex Cover 的 primal-dual 算法

问题定义：

每个顶点 \(v\) 有权重 \(w_v\geq 0\)，目标是找最小权重顶点覆盖

整数规划：

\[ \begin{aligned} \min\quad & \sum_{v\in V}w_vx_v\\ \text{s.t.}\quad & x_u+x_v\geq 1,\quad \forall (u,v)\in E\\ & x_v\in\{0,1\},\quad \forall v\in V \end{aligned} \]

LP 松弛：

\[ \begin{aligned} \min\quad & \sum_{v\in V}w_vx_v\\ \text{s.t.}\quad & x_u+x_v\geq 1,\quad \forall (u,v)\in E\\ & x_v\geq 0,\quad \forall v\in V \end{aligned} \]

对偶为：

\[ \begin{aligned} \max\quad & \sum_{e\in E}y_e\\ \text{s.t.}\quad & \sum_{e\in\delta(v)}y_e\leq w_v,\quad \forall v\in V\\ & y_e\geq 0,\quad \forall e\in E \end{aligned} \]

primal-dual 思路

维护对偶可行解 \(y\)。从未覆盖边中选一条边 \((u,v)\)，同时增加 \(y_{uv}\)，直到 \(u\) 或 \(v\) 的某个顶点约束变紧：

\[ \sum_{e\in\delta(v)}y_e=w_v \]

把变紧的顶点加入覆盖集。

最后得到的顶点集是一个顶点覆盖，并且可证明：

\[ \sum_{v\in C}w_v\leq 2\sum_{e\in E}y_e\leq 2OPT \]

所以 Weighted Vertex Cover 也有 2-approximation。

这个算法比“直接选一条边两个端点”更适合带权情形。

---

TSP 与 Metric TSP

TSP

旅行商问题 (TSP)：

输入一个带边长的图，要求找一条访问每个顶点恰好一次并回到起点的最短 tour。

一般 TSP 很难近似。

一般 TSP 不可近似

若不要求边权满足三角不等式，则对任意常数 \(\alpha\)，求 \(\alpha\)-approximation 都是 NP-hard

证明思路可以从 Hamiltonian Cycle 归约：

给定无权图 \(G=(V,E)\)，构造完全图 \(G'\)：

\[ w(u,v)= \begin{cases} 1 & (u,v)\in E\\ M & (u,v)\notin E \end{cases} \]

其中 \(M\) 取足够大，例如 \(M=\alpha |V|+1\)

若 \(G\) 有 Hamiltonian cycle，则 \(G'\) 有代价 \(|V|\) 的 tour

若 \(G\) 没有 Hamiltonian cycle，则任何 tour 至少用一条原图中不存在的边，代价超过 \(\alpha |V|\)

如果存在 \(\alpha\)-approximation，就能区分这两种情况，从而解 Hamiltonian Cycle，推出 \(\text{P}=\text{NP}\)

Metric TSP

Metric TSP 要求边权满足三角不等式：

\[ w(u,v)\leq w(u,x)+w(x,v) \]

这排除了上面的极端构造，也使得“shortcut”操作不会增加代价

---

Metric TSP 的 2-近似

算法：

1. 求图的最小生成树 \(T\)
2. 把 \(T\) 中每条边复制一份，得到欧拉图
3. 找一条欧拉回路
4. 按欧拉回路中顶点首次出现的顺序 shortcut，得到 Hamiltonian tour

正确性

复制 MST 后，每个顶点度数变为偶数，所以图存在欧拉回路。

shortcut 时跳过已经访问过的顶点。因为满足三角不等式，直接从当前点跳到下一个未访问点不会增加总长度。

近似比分析

任意 TSP tour 删除一条边后得到一棵生成树，所以：

\[ w(T)\leq OPT \]

复制 MST 后欧拉图总代价为：

\[ 2w(T)\leq 2OPT \]

shortcut 不增加代价，因此输出 tour \(C\) 满足：

\[ w(C)\leq 2w(T)\leq 2OPT \]

所以这是一个 2-approximation。

---

Christofides 算法

Christofides 算法将 Metric TSP 的近似比改进到 \(3/2\)。

算法：

1. 求最小生成树 \(T\)
2. 找出 \(T\) 中所有奇度顶点集合 \(O\)
3. 在 \(O\) 上求最小权完美匹配 \(M\)
4. 把 \(M\) 加到 \(T\) 上，得到欧拉多重图
5. 找欧拉回路并 shortcut，得到 tour

为什么加入匹配后是欧拉图

在 \(T\) 中：

• \(O\) 中顶点度数为奇数
• \(V\setminus O\) 中顶点度数为偶数

完美匹配 \(M\) 恰好让 \(O\) 中每个顶点度数增加 1，因此所有顶点度数都变成偶数

匹配代价的上界

设最优 TSP tour 为 \(C^*\)。只看 \(C^*\) 在奇度顶点集合 \(O\) 上的访问顺序，可以把它拆成两个完美匹配。由于二者总代价不超过 \(OPT\)，其中较小的一个代价至多：

\[ \frac{1}{2}OPT \]

而 \(M\) 是最小权完美匹配，所以：

\[ w(M)\leq \frac{1}{2}OPT \]

又因为：

\[ w(T)\leq OPT \]

所以：

\[ w(T)+w(M)\leq \frac{3}{2}OPT \]

shortcut 不增加代价，输出 tour 满足：

\[ w(C)\leq \frac{3}{2}OPT \]

因此 Christofides 算法是 \(3/2\)-approximation

补充

Metric TSP 的 \(3/2\) 界长期非常经典。Euclidean TSP 由于有更强的几何结构，Arora 和 Mitchell 分别给出了 PTAS，一般 Metric TSP 后续也有比 \(3/2\) 略优的随机化结果

---

Set Cover

问题定义

输入：

• 元素全集 \(E=\{e_1,e_2,\ldots,e_n\}\)
• 子集族 \(S_1,S_2,\ldots,S_m\subseteq E\)
• 权重 \(w_1,w_2,\ldots,w_m\geq 0\)

目标是选择一组集合 \(I\subseteq\{1,\ldots,m\}\)，覆盖全集：

\[ \bigcup_{i\in I}S_i=E \]

并最小化：

\[ \sum_{i\in I}w_i \]

Vertex Cover 可以看作 Set Cover 的特殊情况：

• 每条边是一个元素
• 每个顶点对应一个集合，包含与该顶点 incident 的所有边

---

Set Cover 的 LP 舍入

整数规划：

\[ \begin{aligned} \min\quad & \sum_{j=1}^m w_jx_j\\ \text{s.t.}\quad & \sum_{j:e_i\in S_j}x_j\geq 1,\quad \forall e_i\in E\\ & x_j\in\{0,1\},\quad 1\leq j\leq m \end{aligned} \]

LP 松弛：

\[ \begin{aligned} \min\quad & \sum_{j=1}^m w_jx_j\\ \text{s.t.}\quad & \sum_{j:e_i\in S_j}x_j\geq 1,\quad \forall e_i\in E\\ & x_j\geq 0,\quad 1\leq j\leq m \end{aligned} \]

这里不必额外写 \(x_j\leq 1\)。如果某个 LP 最优解中 \(x_j>1\)，把它降到 1 仍然不会破坏覆盖约束，而且会使目标函数不增。因此总可以取一个满足 \(0\leq x_j\leq 1\) 的 LP 最优解。

由于这是把 \(x_j\in\{0,1\}\) 放宽成连续变量，LP 的可行域更大。对最小化问题有：

\[ OPT_{LP}\leq OPT \]

所以 LP 最优值可以作为整数最优值的下界。

设：

\[ f_i=|\{j:e_i\in S_j\}| \]

并令：

\[ f=\max_i f_i \]

解出 LP 最优解 \(x^*\) 后，选择：

\[ I=\{j:x_j^*\geq 1/f\} \]

为什么覆盖所有元素

对任意元素 \(e_i\)，LP 约束给出：

\[ \sum_{j:e_i\in S_j}x_j^*\geq 1 \]

这个求和中最多有 \(f\) 项。如果所有项都小于 \(1/f\)，总和就小于 1，矛盾。

所以至少有一个包含 \(e_i\) 的集合 \(S_j\) 满足 \(x_j^*\geq 1/f\)，会被选中。

近似比

对被选中的集合，有：

\[ 1\leq f x_j^* \]

所以：

\[ \sum_{j\in I}w_j \leq f\sum_{j\in I}w_jx_j^* \leq f\sum_{j=1}^m w_jx_j^* =f\cdot OPT_{LP} \leq f\cdot OPT \]

因此该算法是 \(f\)-approximation。

当每个元素只出现在很少集合中时，这个界很有用。

Vertex Cover 是这个舍入方法的一个特例：把边看成元素，把顶点看成集合，则每条边恰好出现在两个端点集合中，所以 \(f=2\)，阈值舍入就退化为 \(x_v^*\geq 1/2\) 的 2-近似。

---

Set Cover 的贪心算法

Weighted Set Cover 的经典贪心算法：

每一步选择单位新覆盖元素代价最小的集合：

\[ \frac{w_i}{|S_i\cap U|} \]

其中 \(U\) 是当前还未覆盖的元素集合。

GREEDY-SET-COVER(E, S, w)
    U = E
    I = empty
    while U is not empty
        choose S_i minimizing w_i / |S_i cap U|
        I = I union {i}
        U = U - S_i
    return I

调和数界

令：

\[ g=\max_i |S_i| \]

调和数为：

\[ H_g=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{g} \]

则贪心算法是：

\[ H_g\text{-approximation} \]

因为：

\[ H_g\leq 1+\ln g \]

所以也常写成：

\[ (1+\ln g)\text{-approximation} \]

若 \(g\leq n\)，则得到：

\[ O(\log n) \]

近似。

价格法分析

当贪心算法选择集合 \(S_i\) 时，它新覆盖了 \(k=|S_i\cap U|\) 个元素。给每个新覆盖的元素收取价格：

\[ \frac{w_i}{k} \]

最终算法代价等于所有元素价格之和。

考虑最优解中的任意集合 \(S^*\)，大小为 \(d\)。在它的元素被逐步覆盖时，若还剩 \(r\) 个未覆盖元素，贪心选择的单位价格不会超过：

\[ \frac{w(S^*)}{r} \]

因此 \(S^*\) 中元素被收取的总价格至多：

\[ w(S^*)\left(1+\frac{1}{2}+\cdots+\frac{1}{d}\right) \leq H_g w(S^*) \]

对最优解中所有集合求和，即得：

\[ \text{cost(greedy)}\leq H_g\cdot OPT \]

紧性

Set Cover 的 \(\Theta(\log n)\) 近似界基本是紧的。除非 \(\text{P}=\text{NP}\)，不能期望对一般 Set Cover 得到任意常数因子近似。

更强的不可近似结果基于 PCP 定理，说明贪心算法的对数量级本质上已经正确。

---

Dual Fitting 视角

Set Cover 的 LP 对偶是：

\[ \begin{aligned} \max\quad & \sum_{i=1}^n y_i\\ \text{s.t.}\quad & \sum_{e_i\in S_j}y_i\leq w_j,\quad 1\leq j\leq m\\ & y_i\geq 0,\quad 1\leq i\leq n \end{aligned} \]

贪心价格法中的元素价格 \(z_i\) 不一定形成对偶可行解，但把它们缩小 \(H_g\) 倍：

\[ y_i=\frac{z_i}{H_g} \]

可以证明得到对偶可行解。

于是由弱对偶：

\[ \sum_i y_i\leq OPT \]

又因为算法代价为：

\[ \sum_i z_i=H_g\sum_i y_i \]

所以：

\[ \text{cost(greedy)}\leq H_g OPT \]

这就是 dual fitting 的典型用法：先构造一个“差一点可行”的对偶解，再按某个因子缩放成真正可行解。

---

Center Selection / Metric k-center

问题定义

输入 \(n\) 个点：

\[ s_1,s_2,\ldots,s_n \]

要选择 \(k\) 个中心 \(C\)，使得每个点到最近中心的最大距离最小。

定义：

\[ \text{dist}(s_i,C)=\min_{c\in C}\text{dist}(s_i,c) \]

覆盖半径：

\[ r(C)=\max_i \text{dist}(s_i,C) \]

目标：

\[ \min_{|C|=k} r(C) \]

假设距离满足度量性质：

1. \(\text{dist}(x,x)=0\)
2. \(\text{dist}(x,y)=\text{dist}(y,x)\)
3. \(\text{dist}(x,z)\leq \text{dist}(x,y)+\text{dist}(y,z)\)

一个错误贪心

先选一个单中心最优点，再不断加入能最大幅度降低半径的点，这个策略可能任意差。

原因是：局部上最能改善当前半径的点，可能无法为全局簇结构留下足够名额。

---

Farthest-first Traversal

算法：

GREEDY-CENTER-SELECTION(k, s)
    C = empty
    choose an arbitrary first center
    repeat until |C| = k
        choose site s_i maximizing dist(s_i, C)
        C = C union {s_i}
    return C

每次选择离当前中心集合最远的点。

2-近似分析

设算法输出 \(C\)，最优中心集合为 \(C^*\)。

算法终止时，所有点到 \(C\) 的距离至多 \(r(C)\)。并且算法选择的中心两两距离至少为 \(r(C)\)，因为每个新中心都是当时离已有中心最远的点。

反证法。假设：

\[ r(C^*)<\frac{1}{2}r(C) \]

则以最优中心为球心、半径 \(r(C^*)\) 的 \(k\) 个球覆盖所有点。

但算法选出的 \(k\) 个中心两两距离至少 \(r(C)>2r(C^*)\)，所以任意两个算法中心不可能落在同一个最优球中。

于是每个最优球恰好包含一个算法中心。

对任意点 \(s\)，设它所在最优球的中心为 \(c^*\)，该球中的算法中心为 \(c\)。则：

\[ \text{dist}(s,c) \leq \text{dist}(s,c^*)+\text{dist}(c^*,c) \leq 2r(C^*) \]

因此：

\[ r(C)\leq 2r(C^*) \]

与假设 \(r(C)>2r(C^*)\) 矛盾。

所以算法是 2-approximation。

不可近似性

除非 \(\text{P}=\text{NP}\)，Metric \(k\)-center 不存在任何因子小于 2 的多项式时间近似算法。

因此 farthest-first traversal 的 2-近似在常数因子意义下是最优的。

---

MAX-SAT

问题定义

输入：

• 布尔变量 \(x_1,\ldots,x_n\)
• 子句 \(C_1,\ldots,C_m\)
• 每个子句权重 \(w_j\geq 0\)

目标是找一个 TRUE/FALSE 赋值，使得被满足子句的总权重最大。

与 SAT 不同，MAX-SAT 总是有可行解，只是要最大化满足的权重。

---

Johnson 随机算法

最简单的随机算法：

对每个变量独立地以概率 \(1/2\) 赋 TRUE。

设子句 \(C_j\) 中有 \(k_j\) 个不同文字。它不被满足的概率是：

\[ 2^{-k_j} \]

所以被满足的概率是：

\[ 1-2^{-k_j} \]

若每个子句至少有一个文字，则：

\[ 1-2^{-k_j}\geq \frac{1}{2} \]

令随机变量 \(W\) 表示被满足子句的总权重，则由期望线性性：

\[ \mathbb{E}[W] = \sum_{j=1}^m w_j\Pr[C_j\text{ is satisfied}] \geq \frac{1}{2}\sum_{j=1}^m w_j \]

而最优值至多所有子句权重之和：

\[ OPT\leq \sum_{j=1}^m w_j \]

所以：

\[ \mathbb{E}[W]\geq \frac{1}{2}OPT \]

因此这是一个随机 \(1/2\)-approximation。

MAX-E3SAT

若每个子句恰好有 3 个文字，则随机赋值满足一个子句的概率为：

\[ 1-\frac{1}{8}=\frac{7}{8} \]

因此得到 \(7/8\)-approximation。

Hastad 的不可近似结果说明，对 MAX-E3SAT，如果要求超过 \(7/8\) 的近似比，则会推出 \(\text{P}=\text{NP}\)。所以这个简单随机算法在该模型下已经达到最优阈值。

---

MAX-SAT 的 LP 随机舍入

Goemans-Williamson 的经典思路是：先用 LP 决定每个变量取 TRUE 的概率，再随机舍入。

对每个变量 \(x_i\) 建变量 \(y_i\in[0,1]\)，表示 \(x_i\) 被设为 TRUE 的概率。

对每个子句 \(C_j\) 建变量 \(z_j\)，表示子句 \(j\) 是否被满足。

设：

• \(P_j\) 是在 \(C_j\) 中正出现的变量集合
• \(N_j\) 是在 \(C_j\) 中负出现的变量集合

LP 松弛可写成：

\[ \begin{aligned} \max\quad & \sum_j w_jz_j\\ \text{s.t.}\quad & z_j\leq \sum_{i\in P_j}y_i+\sum_{i\in N_j}(1-y_i),\quad \forall j\\ & 0\leq y_i\leq 1,\quad \forall i\\ & 0\leq z_j\leq 1,\quad \forall j \end{aligned} \]

解出 LP 后，独立地令：

\[ \Pr[x_i=\text{TRUE}]=y_i^* \]

单个子句分析

设子句 \(C_j\) 中文字对应的“满足概率贡献”为 \(a_1,\ldots,a_k\)，则该子句未被满足的概率为：

\[ \prod_{\ell=1}^k(1-a_\ell) \]

利用算术平均和几何平均不等式，可以证明：

\[ \Pr[C_j\text{ satisfied}] \geq \left(1-\left(1-\frac{1}{k}\right)^k\right)z_j^* \]

由于：

\[ \left(1-\frac{1}{k}\right)^k\leq \frac{1}{e} \]

所以：

\[ \Pr[C_j\text{ satisfied}] \geq \left(1-\frac{1}{e}\right)z_j^* \]

对所有子句加权求和：

\[ \mathbb{E}[W] \geq \left(1-\frac{1}{e}\right)\sum_j w_jz_j^* \geq \left(1-\frac{1}{e}\right)OPT \]

因此 LP 随机舍入给出：

\[ 1-\frac{1}{e} \]

近似。

Best of Two

Johnson 随机算法对长子句效果好，LP 随机舍入对短子句效果好。

Goemans-Williamson 的 Best-of-Two 思想是：

1. 运行 Johnson 算法
2. 运行 LP rounding 算法
3. 输出两者中满足权重更大的赋值

重新分析可以得到 MAX-SAT 的 \(3/4\)-approximation。

这个例子说明：两个近似算法单独看可能都不是最强，但它们的失败情形互补时，可以通过“取更好者”得到更强保证。

---

Knapsack

问题定义

输入：

• 背包容量 \(B\)
• 物品集合 \(N=\{1,\ldots,n\}\)
• 物品 \(i\) 的大小 \(s_i\geq 0\)
• 物品 \(i\) 的收益 \(p_i\geq 0\)

目标是选择 \(A\subseteq N\)，满足：

\[ s(A)=\sum_{i\in A}s_i\leq B \]

并最大化：

\[ p(A)=\sum_{i\in A}p_i \]

按密度贪心的反例

按收益密度排序：

\[ \frac{p_1}{s_1}\geq \frac{p_2}{s_2}\geq\cdots\geq \frac{p_n}{s_n} \]

然后依次放入能放下的物品。

这个算法本身不是常数近似。例如：

• 物品 1：\(s_1=1,p_1=2\)
• 物品 2：\(s_2=B,p_2=B\)

当 \(B\) 很大时，贪心会先放物品 1，之后放不下物品 2，收益只有 2；最优解收益为 \(B\)。

---

Modified Greedy 的 \(1/2\) 近似

修正算法：

1. 按密度从高到低运行贪心，得到解 \(G\)
2. 找单个收益最大的物品 \(i_{\max}\)
3. 输出 \(G\) 和 \(\{i_{\max}\}\) 中收益更大的一个

设按密度顺序，贪心接受了 \(1,\ldots,k-1\)，第一个放不下的物品是 \(k\)。

分数背包的最优值是 0-1 背包的上界。分数背包会取前 \(k-1\) 个物品，再取物品 \(k\) 的一部分。因此：

\[ OPT \leq \sum_{i=1}^{k-1}p_i+p_k \]

所以：

\[ \max\left\{\sum_{i=1}^{k-1}p_i,\ p_k\right\} \geq \frac{1}{2}OPT \]

因为最大单个物品收益至少为 \(p_k\)，Modified Greedy 输出收益至少为：

\[ \frac{1}{2}OPT \]

因此它是 \(1/2\)-approximation。

---

Knapsack 的 FPTAS

Knapsack 的伪多项式 DP 可以按收益维度写：

令：

\[ DP[i,p]=\text{用前 } i \text{ 个物品获得收益至少 } p \text{ 所需的最小容量} \]

若收益总和为 \(P=\sum_i p_i\)，则时间复杂度为：

\[ O(nP) \]

问题在于 \(P\) 可能很大。

缩放收益

设：

\[ p_{\max}=\max_i p_i \]

给定误差参数 \(\varepsilon>0\)，取缩放因子：

\[ K=\frac{\varepsilon p_{\max}}{n} \]

定义缩放后的整数收益：

\[ \hat{p}_i=\left\lfloor \frac{p_i}{K}\right\rfloor \]

然后对 \(\hat{p}_i\) 运行收益维度 DP。

因为：

\[ \hat{p}_i\leq \frac{p_i}{K}\leq \frac{p_{\max}}{K}=\frac{n}{\varepsilon} \]

所以总缩放收益：

\[ \sum_i\hat{p}_i=O\left(\frac{n^2}{\varepsilon}\right) \]

DP 时间为：

\[ O\left(\frac{n^3}{\varepsilon}\right) \]

近似比

对任意物品集合 \(X\)：

\[ K\hat{p}(X)\leq p(X) \]

且由于每个物品向下取整损失不到 \(K\)：

\[ p(X)<K\hat{p}(X)+nK \]

设 \(A^*\) 是最优解，\(A\) 是缩放 DP 输出。因为 \(A\) 在缩放收益下最优：

\[ \hat{p}(A)\geq \hat{p}(A^*) \]

所以：

\[ p(A)\geq K\hat{p}(A) \geq K\hat{p}(A^*) > p(A^*)-nK \]

又因为：

\[ nK=\varepsilon p_{\max}\leq \varepsilon OPT \]

得到：

\[ p(A)\geq (1-\varepsilon)OPT \]

因此 Knapsack 有 FPTAS。

---

局部搜索补充

近似算法公开课中还常见一类方法：局部搜索 (local search)。

基本框架：

1. 从任意可行解开始
2. 定义邻域，例如交换一个元素、加入一个元素、删除一个元素
3. 如果邻域中存在更好的解，就移动过去
4. 直到没有局部改进

局部搜索适合的问题包括：

• Max-Cut
• facility location
• \(k\)-median 的交换局部搜索
• scheduling 的局部交换

例如 Max-Cut 的简单局部搜索：

若某个点移动到另一侧能增加割边数，就移动它。终止时，每个点至少有一半 incident 边跨过割，因此总割边数至少为：

\[ \frac{1}{2}|E| \]

而最优割最多为 \(|E|\)，所以得到 \(1/2\)-approximation。

局部搜索的难点在于：

• 可能需要证明多项式步终止
• 或者允许近似局部最优
• 需要把“局部最优条件”转化成全局近似保证

---

随机化与去随机化

很多随机近似算法的证明只使用期望值。

如果能证明：

\[ \mathbb{E}[A]\geq \alpha OPT \]

那么至少存在某个随机选择使得：

\[ A\geq \alpha OPT \]

为了得到确定性算法，可以使用：

• 条件期望法
• 枚举小规模随机种子
• pairwise independent 随机变量

条件期望法

以 MAX-SAT 为例，随机赋值有期望保证。可以按顺序固定变量：

1. 对当前变量分别尝试 TRUE 和 FALSE
2. 计算在该选择下，剩余随机变量的条件期望
3. 选择条件期望更大的值

每一步都不降低条件期望，最终得到一个确定性赋值，其目标值至少为初始期望。

因此随机算法有时不仅是分析工具，也能转化成确定性近似算法。

---

不可近似性

近似算法不只研究“能做到什么”，也研究“不能做到什么”。

典型结果包括：

问题	近似情况
一般 TSP	任意常数因子近似都是 NP-hard
Metric \(k\)-center	不存在 \(2-\varepsilon\) 近似，除非 \(\text{P}=\text{NP}\)
Set Cover	很难优于 \(\Theta(\log n)\)
MAX-E3SAT	\(7/8\) 阈值是最优的，除非 \(\text{P}=\text{NP}\)
Knapsack	有 FPTAS
Euclidean TSP	有 PTAS

这些结果说明：不同 NP-hard 优化问题的可近似性差别很大。

为什么同样 NP-hard，近似难度不同

NP-hard 只说明精确求解困难，但不说明近似是否困难。

例如：

• Vertex Cover NP-hard，但有简单 2-近似
• Set Cover NP-hard，能做到 \(O(\log n)\)，但常数近似很难
• Knapsack NP-hard，但有 FPTAS
• 一般 TSP NP-hard，甚至没有任何常数近似

所以近似算法给 NP-hard 问题提供了更细的分类。

---

设计与分析模板

公开课中常用下面的模板来组织近似算法证明。

1. 先找界

对最小化问题，找 \(OPT\) 的下界：

• MST 是 TSP 的下界
• 平均负载和最大作业是 makespan 的下界
• 匹配大小是 Vertex Cover 的下界
• LP 最优值是整数最优值的下界

对最大化问题，找 \(OPT\) 的上界：

• MAX-SAT 的 \(OPT\) 不超过总权重
• Knapsack 的 \(OPT\) 不超过分数背包最优值

2. 再比较算法输出

证明算法输出值不超过下界的 \(\alpha\) 倍，或不小于上界的 \(\alpha\) 倍。

3. 找到结构性解释

很多近似算法的关键不是计算，而是结构：

• Vertex Cover：极大匹配
• Metric TSP：MST、欧拉回路、shortcut
• Christofides：奇度点匹配
• Set Cover：调和数和价格法
• \(k\)-center：三角不等式和鸽巢原理
• Knapsack：分数松弛和收益缩放

4. 检查紧性

一个近似算法分析完成后，还要问：

• 分析是否紧？
• 问题是否有更好的算法？
• 是否存在不可近似下界？

例如：

• List Scheduling 的 \(2-\frac{1}{m}\) 分析基本紧
• Metric \(k\)-center 的 2-近似最优
• Set Cover 的 \(\log n\) 量级基本最优
• Christofides 的 \(3/2\) 不是已知最优不可近似阈值，但长期是经典上界

---

小结

本节主要近似算法：

问题	算法	近似比
Load Balancing	List Scheduling	\(2-\frac{1}{m}\)
Load Balancing	LPT	\(4/3-\frac{1}{3m}\)
Vertex Cover	极大匹配取双端点	\(2\)
Weighted Vertex Cover	primal-dual	\(2\)
Metric TSP	MST doubling	\(2\)
Metric TSP	Christofides	\(3/2\)
Set Cover	LP threshold rounding	\(f\)
Set Cover	Greedy	\(H_g\leq 1+\ln g\)
Metric \(k\)-center	farthest-first traversal	\(2\)
MAX-SAT	随机赋值	\(1/2\)
MAX-E3SAT	随机赋值	\(7/8\)
MAX-SAT	LP randomized rounding	\(1-1/e\)
Knapsack	Modified Greedy	\(1/2\)
Knapsack	profit scaling DP	FPTAS

近似算法的核心是用严格的下界、上界、LP 松弛、随机期望或组合结构，证明算法输出与最优解之间的最坏情况距离。

从这个角度看，近似算法是 NP-hard 优化问题的第二层理论：精确求解不可行时，继续区分哪些问题能常数近似、哪些能 PTAS/FPTAS、哪些只能对数近似、哪些几乎完全不可近似。