基于线性规划的
近似算法设计
LP-Based Approximation Algorithms
关秀翠 · 东南大学数学学院
涵盖：近似算法基础 → 集合覆盖 → LP对偶 → 舍入方法 → 原始-对偶模式 → FPTAS
导论：为什么需要近似算法？
面对 NP-hard 问题的三种策略
策略一：精确算法
分支定界、动态规划、整数规划求解器。适用于小规模实例，但在大规模问题中指数级时间爆炸。
例：用CPLEX求解TSP的n=50实例可能数小时，n=100则需数天。
策略二：启发式算法
模拟退火、遗传算法、局部搜索。速度快但无法给出性能保证，只能通过实验评价。
缺点：无法量化"距离最优有多远"。
策略三：近似算法 ⭐
多项式时间内运行，同时可证明的近似比保证解的质量。
核心优势：理论上可证明的性能保证 + 实践中高效执行。
本课程的独特视角
线性规划 (LP) 是设计近似算法最系统的方法论之一。
LP松驰 + 舍入 或 原始-对偶 = 统一的算法设计范式。
第一章 · 近似算法基础
1.1 启发式算法的三种评价框架
NP优化问题的启发式算法，学术界有三种主流的评价框架：
| 评价方法 | 核心描述 | 优劣分析 |
|---|---|---|
| 经验/实验分析 | 在标准测试集上运行算法，与其他启发式或下界比较 | 结果依赖于测试集的选择，缺乏理论保障 |
| 平均分析 | 假定输入实例服从特定的概率分布，分析算法的平均行为 | 概率分布假设在实际中常常难以满足 |
| 最坏情况分析 | 对所有可能的输入实例给出性能上界 | 理论上最严格、最具说服力 |
1.2 \(\alpha\)-近似比的形式化定义
若算法 \(A\) 在多项式时间内，对所有实例 \(I\) 都有：
\(A(I) \le \alpha \cdot \text{OPT}(I)\)
则称 \(A\) 为 \(\alpha\)-近似算法（\(\alpha \ge 1\)）。
对最大化问题，条件为 \(A(I) \ge \alpha \cdot \text{OPT}(I)\)（\(0 < \alpha \le 1\)）。
近似模式 (Approximation Scheme) 的三层结构
- PTAS（多项式时间近似方案）：对任意固定 \(\varepsilon > 0\)，存在 \((1+\varepsilon)\)-近似算法，时间可随 \(1/\varepsilon\) 指数增长
- FPTAS（完全多项式时间近似方案）：运行时间关于输入规模 \(n\) 和 \(1/\varepsilon\) 均为多项式
- EPTAS：时间形式为 \(f(1/\varepsilon) \cdot n^{O(1)}\)
📝 第一章自测题
共 3 题，点击选项作答，即时反馈
第二章 · 基本问题：集合覆盖与顶点覆盖
2.1 顶点覆盖 (Vertex Cover)
给定无向图 \(G=(V,E)\)，顶点覆盖是顶点子集 \(C \subseteq V\)，使得每条边至少有一个端点在 \(C\) 中。目标：求最小规模的顶点覆盖。
匹配贪心算法（2-近似）
Algorithm: Matching-VertexCover(G)
1. 取 \(G\) 的一条边 \(e = (u,v)\)，将 \(u\) 和 \(v\) 加入覆盖集 \(C\)
2. 删除 \(u\)、\(v\) 及其关联的所有边
3. 重复直到无边剩余
4. 返回 \(C\)
上述算法给出顶点覆盖的 2-近似。算法选出的边构成极大匹配 \(M\)，\(|C| = 2|M|\)。任何顶点覆盖必须至少包含该匹配的每条边的一个端点，即 \(\text{OPT} \ge |M|\)。因此：
\(|C| = 2|M| \le 2 \cdot \text{OPT}\)
顶点覆盖的LP松驰与全单模性
整数规划 (IP)：
\(\min \sum_{v\in V} x_v\)
s.t. \(x_u + x_v \ge 1 \quad \forall (u,v) \in E\)
\(x_v \in \{0,1\}\)
LP松驰：
\(\min \sum_{v\in V} x_v\)
s.t. \(x_u + x_v \ge 1 \quad \forall (u,v) \in E\)
\(0 \le x_v \le 1\)
LP松驰的解可通过"\(x_v \ge 1/2\) 则取 \(v\)"的简单舍入得到 2-近似。对二部图，约束矩阵是全单模的，LP松驰自动给出整数最优解。
2.2 集合覆盖问题 (Set Cover)
给定全集 \(U\) 和子集族 \(\mathcal{S} = \{S_1, \ldots, S_m\}\)（\(\bigcup_i S_i = U\)），每条 \(S_i\) 有权重 \(w_i\)。目标：选择总权最小的子集族覆盖 \(U\) 的全部元素。
基数集合覆盖的贪心算法
Algorithm: GreedySetCover(U, S)
\(C = \emptyset\)
while (\(U \neq \emptyset\))：
选择 \(S_i \in \mathcal{S}\) 使 \(|S_i \cap U|\) 最大
\(U = U \setminus S_i\)
\(C = C \cup \{S_i\}\)
return \(C\)
基数贪心集合覆盖算法是 \(H_n\)-近似的，其中：
\(H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \approx \ln n\)
进一步，在 \(P\neq NP\) 假设下，不存在 \((1-\varepsilon)\ln n\) 以内的近似算法（Feige, 1998）。这意味着贪心算法是渐近最优的。
\(U\) = {11条路段}，每个 \(S_i\) 对应一个哨所覆盖的路段集合。集合覆盖求最少哨所监视全部路段。最小覆盖 \(C = \{S_3, S_4, S_5\}\)，贪心算法按覆盖数从大到小：S1(6条) → S4(5条) → S5(3条) → S3(2条)，输出 \(C = \{S_1, S_4, S_5, S_3\}\)，比最优多用1个。
集合覆盖的对偶形式：击集 (Hitting Set)
对偶视角同样重要——击集问题是在每个子集中至少选一个元素，使所选元素总数最少。顶点覆盖可视作击集的特例：每条边上必须选至少一个顶点。
📝 第二章自测题
共 3 题，点击选项作答，即时反馈
第三章 · 线性规划对偶理论基础
3.1 LP对偶关系与基本定理
对于原始问题 (Primal) 和其对偶问题 (Dual)：
\(\min \; c^T x\)
s.t. \(A x \ge b\)
\(x \ge 0\)
\(\max \; b^T y\)
s.t. \(A^T y \le c\)
\(y \ge 0\)
若 \(x\) 是 (P) 的可行解，\(y\) 是 (D) 的可行解，则：
\(c^T x \ge b^T y\)
原始目标值始终是上界，对偶目标值始终是下界。
若 (P) 有有限最优解 \(x^*\)，则 (D) 也有最优解 \(y^*\)，且：
\(c^T x^* = b^T y^*\)
核心意义：任何原始可行解给出对偶目标值的上界，对偶可行解给出下界。最优时，上下界重合。
3.2 互补松弛条件 (Complementary Slackness)
设 \(x\) 和 \(y\) 分别为 (P) 和 (D) 的可行解，则它们均为最优解当且仅当以下条件同时成立：
对每个 \(j = 1,\ldots,n\)：
\(x_j > 0 \implies \sum_{i} a_{ij} y_i = c_j\)
即：若某原始变量为正，则对应的对偶约束必须紧。
对每个 \(i = 1,\ldots,m\)：
\(y_i > 0 \implies \sum_{j} a_{ij} x_j = b_i\)
即：若某对偶变量为正，则对应的原始约束必须紧。
3.3 经典案例：最大流-最小割的对偶关系
最大流问题 (MFP)
\(\max \; f_{ts}\)
s.t. 容量约束 + 流守恒方程
对偶：最小割
对偶变量可解释为节点势 \(\pi\)，最优时 \(\pi(s)=0, \pi(t)=1\)，中间节点势为 0 或 1，自然形成 s-t 割。
强对偶直接给出 Max-Flow Min-Cut 定理。
这个案例展示了"离散组合结构的对偶刻画"——LP对偶为组合优化中许多 min-max 定理提供了统一的证明框架。
📝 第三章自测题
共 3 题，点击选项作答，即时反馈
第四章 · 基于LP松驰的近似算法
4.1 整性间隙 (Integrality Gap)
对最小化问题，定义：
\(\displaystyle \text{gap} = \sup_{I} \frac{\text{OPT}_{\text{IP}}(I)}{\text{OPT}_{\text{LP}}(I)}\)
整性间隙度量了LP松驰对原问题的"逼近程度"：
- gap = 1：LP松驰是精确的（如二部图匹配、全单模矩阵形）
- gap > 1：存在分数解严格优于任何整数解，需要舍入
- gap 是最根本的下界：任何基于该LP松驰的近似算法，近似比不可能优于 gap
4.2 确定性舍入 (Simple Rounding)
基本思路：求解LP松驰得到分数解 \(\{x_j^*\}\) → 设定阈值 \(\beta\) → 将 \(x_j^* \ge \beta\) 的变量舍入为 1，其余为 0。
Algorithm: RoundingSetCover (f-近似)
1. 求解集合覆盖的LP松驰，得解 \(\{x_S^*\}\)
2. 令 \(f = \max_e |\{S : e \in S\}|\)（任意元素所属的最大子集数）
3. 舍入：对每个子集 \(S\)，若 \(x_S^* \ge 1/f\)，则选入覆盖族 \(C\)
4. return \(C\)
简单舍入给出集合覆盖的 \(f\)-近似。对顶点覆盖，\(f = 2\)（每条边涉及2个顶点），恰好匹配2-近似。对一般的集合覆盖实例，\(f\) 可能很大。
4.3 随机舍入 (Randomized Rounding)
将LP解 \(\{x_j^*\}\) 视为概率分布：以 \(x_j^*\) 的概率独立地选入变量 \(j\)。
Algorithm: RandomizedRoundingSetCover
1. 求解LP松驰，得解 \(\{x_S^*\}\)
2. 以概率 \(x_S^*\) 独立地选择每个子集 \(S\)
3. 重复 \(\lceil c\ln n\rceil\) 轮（\(n = |U|\)）
4. 若某个元素未被覆盖，单独补上
5. return 选出的子集族 \(C\)
随机舍入给出集合覆盖的 \(O(\log n)\)-近似算法，以高概率成立。核心分析工具：Chernoff界 + 联合界 (Union Bound)。
三种舍入方法系统对比
| 方法 | 核心优势 | 主要局限 | 适用场景 |
|---|---|---|---|
| 简单舍入 | 确定性强，易分析 | 近似比与 f 相关，对稠密实例差 | 顶点覆盖等低 f 问题 |
| 随机舍入 | 突破 f 限制，O(log n) | 解是随机的，需要去随机化 | 一般集合覆盖 |
| 原始-对偶 | 无需求解LP，组合性强 | 设计难度高，逐问题构造 | 设施选址等结构性问题 |
📝 第四章自测题
共 3 题，点击选项作答，即时反馈
第五章 · 原始-对偶模式
5.1 从精确到近似：思想的跃迁
原始-对偶模式最初用于精确算法（如网络流、匹配），其威力在于同时维护原始和对偶变量的增量更新。在近似算法中，核心创新是松弛互补松弛条件，允许"近似紧"而非"严格紧"。
Primal-Dual Schema (通用框架)
1. 初始化：原始解 \(x = 0\)，对偶解 \(y = 0\)
2. while (\(x\) 不是可行的原始解)：
选择并增加某个对偶变量 \(y_i\)
当某个原始约束变紧（近似紧）时，设置相应 \(x_j\)
3. return \(x\)
5.2 松弛互补松弛条件：从精确到近似
原始侧松弛：若 \(x_j > 0\)，则对偶约束"接近紧"：
\(\displaystyle \sum_i a_{ij}y_i \le \beta \cdot c_j\)
对偶侧松弛：若 \(y_i > 0\)，则原始约束"接近紧"：
\(\displaystyle \sum_j a_{ij}x_j \le \alpha \cdot b_i\)
若原始整数解 \(x\) 和对偶可行解 \(y\) 满足 \((\alpha, \beta)\)-松弛互补条件，则 \(x\) 是 \(\alpha \beta\)-近似的：
\(c^T x \le \alpha\beta \cdot b^T y \le \alpha\beta \cdot \text{OPT}\)
5.3 集合覆盖的原始-对偶算法（f-近似）
原始 (Primal)：
\(\min \sum_S w_S x_S\)
s.t. \(\sum_{S:e\in S} x_S \ge 1 \quad \forall e\)
\(x_S \ge 0\)
对偶 (Dual)：
\(\max \sum_e y_e\)
s.t. \(\sum_{e\in S} y_e \le w_S \quad \forall S\)
\(y_e \ge 0\)
Algorithm: PD-SetCover (f-近似)
\(y = 0\); \(C = \emptyset\)
while (\(C\) 未覆盖所有元素)：
选一个未覆盖元素 \(e\)
增加 \(y_e\) 直到某个子集 \(S\) 的对偶约束变紧
\(C = C \cup \{S\}\)
return \(C\)
原始-对偶集合覆盖算法是 \(f\)-近似的，等价于简单舍入的近似比，但算法更简洁且无需LP求解器。
5.4 推广：约束多集覆盖 (Constrained Set Multicover)
每个元素 \(e\) 需要被覆盖至少 \(r_e\) 次，每个子集 \(S\) 最多被选 \(b_S\) 次。原始-对偶模式可直接推广，通过逐元素逐步满足覆盖需求的方式，近似比同样为 \(f\)。
📝 第五章自测题
共 3 题，点击选项作答，即时反馈
第六章 · 度量无容量设施选址问题
6.1 问题描述与整数规划建模
给定：设施集合 \(F\)（开设费用 \(f_i\)），客户集合 \(C\)（城市），设施 \(i\) 到客户 \(j\) 的距离（连接成本）\(c_{ij}\)，且满足三角不等式 \(c_{ik} \le c_{ij} + c_{jk}\)。
目标：选择开设哪些设施 + 每个客户连接到哪个设施，使总成本 = 开设费 + 连接成本最小。
整数规划 (IP) 模型
变量：\(y_i \in \{0,1\}\)（是否开设设施 \(i\)），\(x_{ij} \in \{0,1\}\)（客户 \(j\) 是否连接到设施 \(i\)）
\(\min \; \sum_{i\in F} f_i y_i + \sum_{i\in F}\sum_{j\in C} c_{ij} x_{ij}\)
s.t. \(\sum_{i\in F} x_{ij} \ge 1 \quad \forall j\) （每个客户必须被服务）
\(x_{ij} \le y_i \quad \forall i,j\) （客户只能连接到已开设的设施）
\(x_{ij}, y_i \in \{0,1\}\)
6.2 Jain-Vazirani 原始-对偶算法（3-近似）
LP对偶引入变量 \(\alpha_j\)（客户 \(j\) 的"预算"/对偶变量）和 \(\beta_{ij}\)。算法沿"时间轴"直觉运行：
Algorithm: PD-FacilityLocation (Jain-Vazirani, 2001)
1. 所有客户 \(j\) 的预算 \(\alpha_j = 0\)，时间 \(t = 0\)
2. while (存在未连接的客户)：
增加所有未连接客户的 \(\alpha_j\)（预算增长）
当 \(\sum_j \max(0, \alpha_j - c_{ij}) = f_i\) 时，开设设施 \(i\)
当某客户 \(j\) 的预算达到某已开设施 \(i\) 的成本 \(c_{ij}\)，连接 \(j \to i\)
3. return 开设的设施集 + 连接方案
上述原始-对偶算法给出度量UFL的 3-近似，运行时间 \(O(m \log m)\)，\(m = |F| \times |C|\)。后续 Li (2011) 改进至 1.861-近似，目前最佳为 1.488 (Li, 2013)。
△ 设施选址原始-对偶过程示意：客户预算随时间增长，累计预算足以支付设施时，设施被开设；客户被逐步连接。
📝 第六章自测题
共 3 题，点击选项作答，即时反馈
第七章 · 子集求和问题的FPTAS
7.1 问题描述与精确指数算法
给定正整数集合 \(S = \{x_1, x_2, \ldots, x_n\}\) 和目标值 \(t\)，求 \(S\) 的一个子集，使其元素和不超过 \(t\) 且尽可能大。
子集求和是NP完全问题（通过划分问题归约），但它是弱NP完全的——存在关于 \(n\) 和 \(t\) 的伪多项式时间动态规划。
精确指数算法 ExactSubsetSum
Algorithm: ExactSubsetSum(S, t)
\(L[0] = \{0\}\)
for \(i = 1\) to \(n\)：
\(L[i] = \text{mergeLists}(L[i-1], L[i-1] + x_i)\)
删除 \(L[i]\) 中超过 \(t\) 的元素
return \(\max(L[n])\)
核心洞察：\(L[i]\) 存储 \(\{x_1, \ldots, x_i\}\) 的所有可能子集和。\(|L[i]| \le 2^i\)，因此是指数时间的。
\(P_0 = \{0\} \to P_1 = \{0, 1\} \to P_2 = \{0, 1, 4, 5\} \to P_3 = \{0, 1, 4, 5, 6, 9, 10\}\)
7.2 基于修整技术的FPTAS（方法一）
关键思想：对 \(L[i]\) 进行"修整"(trim)，用参数 \(\delta\) 控制精度，使列表大小保持在多项式级别。
从 \(L\) 中删去尽可能多的元素，使每个被删元素 \(y\) 在修整后的表中都有一个代表 \(z\) 满足：
\((1-\delta) y \le z \le y\)
每次修整引入的相对误差不超过 \(\delta\)，\(n\) 次累加后的总误差界为 \(\varepsilon = n\delta\)。
修整结果：\(L_1 = \langle 10, 12, 15, 20, 23, 29 \rangle\)，其中 11→10, 21/22→20, 24→23 被代表。
Algorithm: ApproxSubsetSum(S, t, \(\varepsilon\))
\(n = |S|\); \(L[0] = \{0\}\)
for \(i = 1\) to \(n\)：
\(L[i] = \text{Merge-Lists}(L[i-1], L[i-1] + S[i])\)
\(L[i] = \text{Trim}(L[i], \varepsilon/n)\)
删除 \(L[i]\) 中超过 \(t\) 的元素
return \(\max(L[n])\)
ApprovSubsetSum 是子集求和问题的 FPTAS：近似解与最优解的相对误差 \(\le \varepsilon\)，运行时间 \(O(n^2 / \varepsilon)\)，关于 \(n\) 和 \(1/\varepsilon\) 均为多项式。
7.3 基于动态规划的FPTAS（方法二）
第二种构造思路：先用动态规划精确求解子集求和（伪多项式时间 \(O(n \cdot t)\)），然后通过数值缩放降低状态空间：
\(x_i' = \lfloor x_i \cdot n / (\varepsilon \cdot t) \rfloor\)
在新尺度上运行DP：状态空间从 \(O(t)\) 缩小到 \(O(n/\varepsilon)\)，缩放引入的相对误差由 \(\varepsilon\) 控制。
| 方法 | 核心技术 | 时间复杂度 | 教学价值 |
|---|---|---|---|
| 修整法 | 合并列表+修整删减 | \(O(n^2/\varepsilon)\) | 理解"舍入→可控误差"的经典范例 |
| DP缩放法 | 数值缩放+DP递推 | \(O(n^2/\varepsilon)\) | 可推广到更多伪多项式DP问题 |
📝 第七章自测题
共 3 题，点击选项作答，即时反馈
总结 · 方法论全景
知识图谱
四种核心技术系统对比
| 技术 | 核心操作 | 典型问题 | 近似比 | 是否需LP求解器 |
|---|---|---|---|---|
| LP松驰 + 舍入 | 求解LP → 舍入分数解 | 集合覆盖、顶点覆盖 | \(f\) 或 \(O(\log n)\) | 需要 |
| 随机舍入 | 以LP解为概率选取 → 去随机化 | 集合覆盖、MAX-SAT | \(O(\log n)\) | 需要 |
| 原始-对偶模式 | 同时迭代构造原始+对偶可行解 | 集合覆盖、设施选址、Steiner树 | \(f\) 或 3 | 不需要 |
| FPTAS技术 | 舍入/缩放 + DP | 子集求和、背包、调度 | \(1+\varepsilon\) | 不需要 |
四大关键定理
弱对偶定理：任何原始和对偶可行解给出目标值的上下界
强对偶定理：最优时原始与对偶目标值相等，\(c^Tx^*=b^Ty^*\)
Chvátal定理：贪心集合覆盖是 \(H_n\)-近似，且不可改进
Jain-Vazirani定理：度量UFL存在3-近似原始-对偶算法
- 半定规划 (SDP) 在近似算法中的应用 — Goemans-Williamson MAX-CUT算法
- 不可近似性理论与PCP定理
- Unique Games Conjecture与最优近似比的确定
- 在线算法与竞争比分析
- 动态规划 + 原始-对偶混合方法（Steiner树、k-中位问题）