基于线性规划的图最小带权点覆盖问题的原始-对偶近似算法求解示例
我将为您讲解线性规划在图算法中的一个经典应用：如何用原始-对偶方法设计近似算法来求解“最小带权点覆盖”问题。我们循序渐进地讲解。
1. 问题描述
最小带权点覆盖问题：
- 给定一个无向图 \(G = (V, E)\)，其中每个顶点 \(v \in V\) 有一个正权值 \(w(v) > 0\)。
- 目标是找到一个顶点子集 \(S \subseteq V\)，使得每条边 \(e \in E\) 至少有一个端点在 \(S\) 中（即 \(S\) 是一个点覆盖），并且所选顶点总权值 \(\sum_{v \in S} w(v)\) 尽可能小。
这是一个经典的 NP-hard 问题。当所有权值相同时，是标准的最小点覆盖问题。我们希望通过线性规划松弛和原始-对偶方法，设计一个能在多项式时间内运行、并保证近似比（解的质量上界）的算法。
2. 整数规划建模
我们为每个顶点 \(v\) 引入一个 0/1 决策变量 \(x_v\)：
\[x_v = \begin{cases} 1, & \text{如果顶点 } v \text{ 被选中进入点覆盖集合 } S, \\ 0, & \text{否则}. \end{cases} \]
整数规划模型：
\[\begin{aligned} \min \quad & \sum_{v \in V} w(v) x_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} \]
- 目标函数：最小化所选顶点总权值。
- 约束条件：对每条边 \((u,v)\)，至少有一个端点的 \(x\) 值为 1（即至少有一个顶点在覆盖中）。
3. 线性规划松弛与对偶
松弛整数约束，得到线性规划（LP）松弛：
\[\begin{aligned} \min \quad & \sum_{v \in V} w(v) x_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} \]
注意这里去掉了 \(x_v \leq 1\) 的限制，因为如果 \(x_v > 1\)，必然不最优（会增加目标值）。实际上最优解中一定有 \(x_v \le 1\)。
构造其对偶问题：
- 为每条边 \(e = (u,v) \in E\) 引入对偶变量 \(y_e \ge 0\)。
- 对偶线性规划为：
\[\begin{aligned} \max \quad & \sum_{e \in E} y_e \\ \text{s.t.} \quad & \sum_{e: v \in e} y_e \leq w(v), \quad \forall v \in V, \\ & y_e \geq 0, \quad \forall e \in E. \end{aligned} \]
- 解释：对偶变量 \(y_e\) 可以理解为边 \(e\) 的“价格”或“收益”。约束条件是说，对于每个顶点 \(v\)，关联到它的所有边的 \(y_e\) 之和不超过该顶点的权值 \(w(v)\)。目标函数是最大化所有边的总价格。
4. 原始-对偶近似算法思想
原始-对偶方法常用于设计组合优化问题的近似算法，其一般步骤是：
- 从原始可行解（通常全为 0）和对偶可行解（通常全为 0）开始。
- 逐步增加对偶变量（“提升”对偶解），直到某些对偶约束变为紧的（等号成立）。
- 根据紧约束选取原始解（顶点），构造一个整数可行解（点覆盖）。
- 证明这个整数解的总权值不超过对偶目标值的某个倍数，从而得到近似比保证。
5. 具体算法步骤
算法：最小带权点覆盖的原始-对偶近似算法
-
初始化：
- 设原始变量 \(x_v = 0\)（对所有 \(v \in V\)）。
- 设对偶变量 \(y_e = 0\)（对所有 \(e \in E\)）。
- 设边集合 \(E' = E\)（初始为所有边）。
-
循环迭代：
- 只要 \(E'\) 非空（即还有未被覆盖的边），执行：
a. 选择一条边 \(e = (u,v) \in E'\)。
b. 同时增加 \(y_e\)，直到存在某个顶点 \(p \in \{u,v\}\) 使得其关联边的 \(y\) 之和等于其权值 \(w(p)\)（即对偶约束变为紧的）。记录这个顶点 \(p\)。
c. 将 \(p\) 加入点覆盖集合 \(S\)（即令 \(x_p = 1\)）。
d. 从 \(E'\) 中移除所有与 \(p\) 相关联的边（因为它们已被覆盖）。
- 只要 \(E'\) 非空（即还有未被覆盖的边），执行：
-
输出：集合 \(S\) 即为点覆盖。
6. 算法演示（简单例子）
考虑一个三角形图（3 个顶点 \(a,b,c\)，边 \((a,b), (b,c), (a,c)\)），权值：\(w(a)=3, w(b)=4, w(c)=5\)。
- 初始化：\(x_a=x_b=x_c=0\)，\(y_{ab}=y_{bc}=y_{ac}=0\)，\(E' = \{(a,b),(b,c),(a,c)\}\)。
- 迭代 1：
- 选边 \((a,b)\)，增加 \(y_{ab}\)。
- 约束检查：顶点 \(a\) 的约束：\(y_{ab} + y_{ac} \le 3\)，顶点 \(b\) 的约束：\(y_{ab}+y_{bc} \le 4\)。
- 增加 \(y_{ab}\) 到 3 时，顶点 \(a\) 的约束变紧（因为目前 \(y_{ac}=0\)，所以 \(y_{ab}=3\) 时等于 \(w(a)=3\)）。
- 将 \(a\) 加入 \(S\)，\(x_a=1\)。
- 从 \(E'\) 中移除与 \(a\) 相关的边：\((a,b)\) 和 \((a,c)\)。现在 \(E' = \{(b,c)\}\)。
- 迭代 2：
- 选边 \((b,c)\)，增加 \(y_{bc}\)。
- 顶点 \(b\) 的约束：目前 \(y_{ab}=3\) 已计入，但 \(b\) 尚未被选，约束为 \(y_{ab}+y_{bc} \le 4\) 即 \(3 + y_{bc} \le 4\)，所以 \(y_{bc}\) 最多增加到 1 就会使顶点 \(b\) 的约束变紧。
- 顶点 \(c\) 的约束：\(y_{bc} + y_{ac} \le 5\)，目前 \(y_{ac}=0\)，所以 \(y_{bc}\) 增加到 1 不会使 \(c\) 的约束变紧。
- 因此增加 \(y_{bc}\) 到 1，顶点 \(b\) 约束变紧。
- 将 \(b\) 加入 \(S\)，\(x_b=1\)。
- 移除边 \((b,c)\)，\(E'\) 变为空。
- 算法结束，输出 \(S = \{a,b\}\)。
- 总权值 = \(3+4=7\)。
7. 算法正确性与近似比分析
正确性：
- 每次迭代，算法至少选择一条未被覆盖的边，并将其至少一个端点加入 \(S\)。
- 当算法终止时，所有边至少有一个端点在 \(S\) 中，所以 \(S\) 是一个点覆盖。
近似比证明（近似比 = 2）：
- 设算法输出的点覆盖为 \(S\)，其总权值为 \(\sum_{v \in S} w(v)\)。
- 算法过程中，当我们把顶点 \(v\) 加入 \(S\) 时，必定是因为存在一条边 \(e\) 使得增加 \(y_e\) 导致 \(v\) 的对偶约束变紧，即：
\[ \sum_{e: v \in e} y_e = w(v). \]
- 因此，对每个 \(v \in S\)，有 \(w(v) = \sum_{e: v \in e} y_e\)。
- 于是：
\[ \sum_{v \in S} w(v) = \sum_{v \in S} \sum_{e: v \in e} y_e. \]
- 交换求和顺序，上式等于 \(\sum_{e \in E} y_e \cdot |\{v \in S : v \in e\}|\)。
- 对每条边 \(e = (u,v)\)，算法保证至少有一个端点在 \(S\) 中，但可能两个端点都在 \(S\) 中（即一条边可能被两个顶点覆盖）。
- 所以 \(|\{v \in S : v \in e\}| \le 2\)。
- 因此：
\[ \sum_{v \in S} w(v) \le 2 \sum_{e \in E} y_e. \]
- 由线性规划弱对偶定理，任意对偶可行解的目标值 \(\sum_{e} y_e\) 不超过原始线性规划松弛的最优值 \(OPT_{LP}\)。
- 而原始整数规划的最优值 \(OPT_{IP} \ge OPT_{LP}\)。
- 所以：
\[ \sum_{v \in S} w(v) \le 2 \cdot OPT_{LP} \le 2 \cdot OPT_{IP}. \]
- 因此，算法是 2-近似的。
8. 算法复杂度与特点
- 每次迭代至少覆盖一条边，至多 \(|E|\) 次迭代。
- 每次迭代中，增加一条边的对偶变量直到某个顶点约束变紧，这可以在常数时间内通过比较相关顶点的“剩余权值”实现。
- 总复杂度为 \(O(|E|)\)（如果使用合适的数据结构跟踪每个顶点的当前对偶约束和程度）。
- 这是一个非常简洁、高效的组合算法，不需求解线性规划，但利用了对偶理论来保证近似比。
9. 小结
我们通过以下步骤解决了最小带权点覆盖问题的近似算法设计：
- 建立整数规划模型。
- 松弛为线性规划，写出对偶问题。
- 设计原始-对偶迭代算法：从对偶全 0 开始，逐步增加对偶变量，当对偶约束变紧时选择顶点，并覆盖相关边。
- 证明了算法输出是可行点覆盖，且总权值不超过最优解的 2 倍（2-近似）。
- 该算法是高效的组合算法，复杂度为 \(O(|E|)\)。
这个示例展示了如何将线性规划对偶理论与组合算法设计巧妙结合，得到具有理论保证的近似算法。