基于线性规划的图最小顶点覆盖问题的原始-对偶近似算法求解示例

我将通过一个具体问题来讲解如何用原始-对偶方法求解图的最小顶点覆盖问题。考虑下图：

顶点集: {1,2,3,4}
边集: (1,2), (1,3), (2,3), (2,4), (3,4)

问题描述
最小顶点覆盖问题要求找到一个顶点子集，使得图中每条边至少有一个端点在该子集中，且顶点数量最少。这是一个NP难问题，但可以通过线性规划的原始-对偶方法获得2-近似解。

线性规划建模

原始问题（松弛版）：

最小化 ∑xᵢ (i=1到4)
满足：
x₁ + x₂ ≥ 1  (边(1,2))
x₁ + x₃ ≥ 1  (边(1,3))  
x₂ + x₃ ≥ 1  (边(2,3))
x₂ + x₄ ≥ 1  (边(2,4))
x₃ + x₄ ≥ 1  (边(3,4))
xᵢ ≥ 0

对偶问题：

最大化 ∑yₑ (e∈E)
满足：
∑yₑ ≤ 1  (对于每个顶点i，对所有与i相连的边)
yₑ ≥ 0

原始-对偶算法求解过程

步骤1：初始化

• 设置所有原始变量 xᵢ = 0
• 设置所有对偶变量 yₑ = 0
• 设置覆盖集 C = ∅

步骤2：迭代提升对偶变量

第一次迭代：

• 选择未覆盖边 (1,2)，提升其对应的对偶变量 y₁₂
• 同时提升 y₁₂ 直到某个约束变紧
• 约束 x₁ + x₂ ≥ 1 对应的对偶约束：y₁₂ + y₁₃ ≤ 1 (顶点1)，y₁₂ + y₂₃ + y₂₄ ≤ 1 (顶点2)
• 当 y₁₂ = 1 时，顶点1和顶点2的约束都变紧
• 将顶点1和顶点2加入覆盖集 C = {1,2}
• 更新 x₁ = 1, x₂ = 1

检查覆盖情况：

• 边(1,2): 顶点1覆盖 ✓
• 边(1,3): 顶点1覆盖 ✓
• 边(2,3): 顶点2覆盖 ✓
• 边(2,4): 顶点2覆盖 ✓
• 边(3,4): 未覆盖 ✗

步骤3：继续迭代

第二次迭代：

• 选择未覆盖边 (3,4)，提升 y₃₄
• 约束 x₃ + x₄ ≥ 1 对应的对偶约束：y₁₃ + y₂₃ + y₃₄ ≤ 1 (顶点3)，y₂₄ + y₃₄ ≤ 1 (顶点4)
• 当 y₃₄ = 1 时，顶点3和顶点4的约束都变紧
• 将顶点3和顶点4加入覆盖集 C = {1,2,3,4}
• 更新 x₃ = 1, x₄ = 1

步骤4：结果分析

覆盖集 C = {1,2,3,4}，大小 = 4
目标函数值 = x₁ + x₂ + x₃ + x₄ = 4

对偶目标函数值 = y₁₂ + y₁₃ + y₂₃ + y₂₄ + y₃₄ = 1 + 0 + 0 + 0 + 1 = 2

近似比分析
原始解值 = 4，对偶解值 = 2
由于对偶解值 ≤ 最优解值 ≤ 原始解值，且原始解值 ≤ 2 × 对偶解值
因此该算法是2-近似算法

算法总结
原始-对偶方法通过同时构造原始可行解和对偶可行解，利用它们之间的关系获得近似解。在这个例子中，虽然找到了所有顶点的覆盖（实际上是最优解），但算法保证找到的解不会超过最优解的2倍。