因此，$ 1 \le 2 x_v^* $ 对于 $ v \in S $ 成立。于是：

这里，第一个不等号是因为当 $ v \in S $ 时 $ 1 \le 2x_v^* $，第二个不等号是因为对更多非负项求和，值不会减小。

因此，算法得到的顶点覆盖大小最多是最优解的两倍。我们说这个算法的**近似比是2**。这是一个经典结果，表明基于LP松弛的简单舍入可以为最小顶点覆盖问题提供一个2-近似算法。

这个整数规划的最优解显然是选择顶点2（即 $ x_2=1, x_1=x_3=0 $），覆盖了两条边，总代价为1。所以 $ OPT_{ILP} = 1 $。

我们可以用观察法求解。由于目标是最小化和，我们希望变量尽可能小，但必须满足约束。从对称性看，让 $ x_1 = x_3 = 0.5, x_2 = 0.5 $ 可以满足约束（因为 $ 0.5+0.5=1 $），且目标值为 $ 0.5+0.5+0.5 = 1.5 $。能否更小？如果 $ x_2 < 0.5 $，那么为了满足第一条约束 $ x_1 + x_2 \ge 1 $，必须有 $ x_1 > 0.5 $；同理，为了满足第二条约束，必须有 $ x_3 > 0.5 $。这样目标值至少为 $ x_1 + x_2 + x_3 > 0.5 + 0.5 + 0.5 = 1.5 $。所以 $ x_1 = x_2 = x_3 = 0.5 $ 确实是最优解。因此，$ OPT_{LP} = 1.5 $。验证了 $ OPT_{LP} \le OPT_{ILP} $ 不成立？等等，这里 $ 1.5 > 1 $，似乎矛盾？注意，是 $ OPT_{LP} \le OPT_{ILP} $ 吗？不对，因为LP是松弛，可行域比ILP大，其最优值应该**小于或等于**ILP的最优值。但这里 $ 1.5 > 1 $。我检查一下：原ILP最优解是 $ x=(0,1,0) $，目标值为1。这个解在LP中可行吗？可行，因为 $ 0,1,0 $ 都满足 $ \ge 0 $。所以LP可行域包含这个整数解，那么LP的最优值应该 ≤ 1。为什么我算出来是1.5？因为 $ x=(0.5,0.5,0.5) $ 的目标值是1.5，比1大，说明它不是最优的。实际上，LP的另一个可行解是 $ x=(0,1,0) $，目标值为1。那么 $ x=(0.5,0.5,0.5) $ 目标值1.5 > 1，所以它不是最优。真正的LP最优解是什么呢？考虑 $ x_2 $ 是关键。设 $ x_2 = a $，则从第一个约束 $ x_1 \ge 1-a $，第二个约束 $ x_3 \ge 1-a $。目标函数为 $ x_1 + a + x_3 \ge (1-a) + a + (1-a) = 2 - a $。我们要最小化，所以希望 $ a $ 尽量大。但 $ a $ 最大能为1（因为从整数解看）。如果 $ a=1 $，那么 $ x_1 \ge 0, x_3 \ge 0 $，取 $ x_1=x_3=0 $，目标值为1。如果 $ a<1 $，比如 $ a=0.8 $，则 $ x_1 \ge 0.2, x_3 \ge 0.2 $，目标值至少为 $ 0.2+0.8+0.2=1.2 > 1 $。所以最优解确实是 $ a=1, x_1=x_3=0 $，即 $ x=(0,1,0) $，$ OPT_{LP} = 1 $。所以之前我误算了一个非最优的分数解。实际上，这个简单的图中，LP的最优解就是整数解。所以 $ OPT_{LP} = OPT_{ILP} = 1 $。

基于线性规划的图最小顶点覆盖问题的贪心算法与近似比分析示例 题目描述 我们考虑一个无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集，\( E \) 是边集。一个顶点覆盖（Vertex Cover）是一个顶点子集 \( S \subseteq V \)，使得图中的每条边至少有一个端点在 \( S \) 中。最小顶点覆盖问题（Minimum Vertex Cover Problem, MVC）的目标是找到一个顶点数量最少的顶点覆盖。这是一个经典的NP-hard问题。在本示例中，我们不仅介绍如何为MVC建立整数线性规划模型，还会深入讲解其线性规划松弛，并重点设计一个基于松弛解的简单贪心算法。我们将详细分析这个算法的步骤、近似比，并通过一个小例子展示完整计算过程。 解题过程循序渐进讲解 第一步：问题建模（整数线性规划） 对于一个无向图 \( G = (V, E) \)，我们为每个顶点 \( v \in V \) 引入一个决策变量 \( x_ v \in \{0, 1\} \)： 如果 \( x_ v = 1 \)，表示顶点 \( v \) 被选入顶点覆盖集合 \( S \)。 如果 \( x_ v = 0 \)，表示顶点 \( v \) 未被选中。 对于每条边 \( e = (u, v) \in E \)，为了使其被覆盖，我们要求其两个端点 \( u \) 和 \( v \) 中至少有一个对应的变量为1。因此，约束条件为： \[ x_ u + x_ v \ge 1 \quad \forall (u, v) \in E \] 我们的目标是最小化被选中顶点的总数量： \[ \min \sum_ {v \in V} x_ v \] 这样，我们得到了最小顶点覆盖问题的 整数线性规划（ILP）模型 ： \[ \begin{aligned} \text{minimize} \quad & \sum_ {v \in V} x_ v \\ \text{subject to} \quad & x_ u + x_ v \ge 1, \quad \forall (u, v) \in E \\ & x_ v \in \{0, 1\}, \quad \forall v \in V \end{aligned} \] 由于变量是整数（0或1），这个优化问题是NP-hard的。 第二步：线性规划松弛 为了得到一个可在线性时间内求解的模型，我们进行 线性规划松弛 ：将变量 \( x_ v \) 的整数约束 \( x_ v \in \{0, 1\} \) 松弛为连续约束 \( 0 \le x_ v \le 1 \)。实际上，由于最小化目标和约束 \( x_ u + x_ v \ge 1 \)，最优解会自动满足 \( x_ v \le 1 \)，所以上界约束可以省略。我们得到 线性规划（LP）松弛模型 ： \[ \begin{aligned} \text{minimize} \quad & \sum_ {v \in V} x_ v \\ \text{subject to} \quad & x_ u + x_ v \ge 1, \quad \forall (u, v) \in E \\ & x_ v \ge 0, \quad \forall v \in V \end{aligned} \] 这个线性规划是多项式时间可解的（例如使用单纯形法或内点法）。设其最优解为 \( x^* = (x_ v^ ) {v \in V} \)，最优目标值为 \( OPT {LP} = \sum_ {v \in V} x_ v^ \)。对于原整数规划的最优解 \( OPT_ {ILP} \)，由于可行域扩大，有 \( OPT_ {LP} \le OPT_ {ILP} \)。 第三步：基于线性规划松弛的贪心舍入算法 我们不能直接使用分数解 \( x^* \)，因为它不一定满足整数约束。一个经典的近似算法思想是 阈值舍入 。我们将设计一个简单的贪心舍入规则： 算法步骤： 求解线性规划松弛 ：求解上述LP模型，得到最优分数解 \( x^* = (x_ v^* )_ {v \in V} \)。 设定阈值并舍入 ：选择一个舍入阈值 \( \theta \in (0, 1 ] \)。常见且简单的选择是 \( \theta = 0.5 \)。 构造整数解 ：对于每个顶点 \( v \in V \)， 如果 \( x_ v^* \ge \theta \)，则将 \( x_ v \) 舍入为1（即将顶点 \( v \) 加入覆盖集 \( S \)）。 如果 \( x_ v^* < \theta \)，则将 \( x_ v \) 舍入为0（不加入）。 输出 ：输出顶点覆盖集合 \( S = \{ v \in V \mid x_ v^* \ge \theta \} \)。 第四步：算法可行性证明 我们需要证明算法输出的集合 \( S \) 确实是一个顶点覆盖。 考虑任意一条边 \( e = (u, v) \in E \)。由线性规划约束，有 \( x_ u^* + x_ v^* \ge 1 \)。 如果 \( x_ u^* \) 和 \( x_ v^* \) 都小于阈值 \( \theta \)，即 \( x_ u^* < \theta \) 且 \( x_ v^* < \theta \)，那么 \( x_ u^* + x_ v^* < 2\theta \)。 当 \( \theta = 0.5 \) 时，这意味着 \( x_ u^* + x_ v^* < 1 \)，这与LP约束 \( x_ u^* + x_ v^* \ge 1 \) 矛盾。 因此，对于任意边 \( (u, v) \)，不可能出现 \( x_ u^* < 0.5 \) 和 \( x_ v^* < 0.5 \) 同时成立。至少有一个端点的 \( x^* \) 值 \( \ge 0.5 \)，从而被舍入为1，该边被覆盖。 因此，\( S \) 是一个合法的顶点覆盖。 第五步：近似比分析（性能保证） 近似比是算法得到的解的大小 \( |S| \) 与最优整数解 \( OPT_ {ILP} \) 的比值上界。我们来分析当 \( \theta = 0.5 \) 时的近似比。 算法解的大小 ：\( |S| \) 等于满足 \( x_ v^* \ge 0.5 \) 的顶点个数。我们可以将其与LP最优值联系起来： \[ |S| = \sum_ {v \in S} 1 \quad \text{且当 } v \in S \text{ 时，} x_ v^* \ge 0.5 \] 因此，\( 1 \le 2 x_ v^* \) 对于 \( v \in S \) 成立。于是： \[ |S| = \sum_ {v \in S} 1 \le \sum_ {v \in S} 2 x_ v^* \le \sum_ {v \in V} 2 x_ v^* = 2 \cdot OPT_ {LP} \] 这里，第一个不等号是因为当 \( v \in S \) 时 \( 1 \le 2x_ v^* \)，第二个不等号是因为对更多非负项求和，值不会减小。 与最优解比较 ：由于 \( OPT_ {LP} \le OPT_ {ILP} \)，我们有： \[ |S| \le 2 \cdot OPT_ {LP} \le 2 \cdot OPT_ {ILP} \] 因此，算法得到的顶点覆盖大小最多是最优解的两倍。我们说这个算法的 近似比是2 。这是一个经典结果，表明基于LP松弛的简单舍入可以为最小顶点覆盖问题提供一个2-近似算法。 第六步：完整示例演算 让我们通过一个具体的图来演示整个过程。 图结构 ：考虑一个简单的路径图 \( P_ 3 \)：三个顶点 \( V = \{1, 2, 3\} \)，两条边 \( E = \{(1,2), (2,3)\} \)。 建立整数规划模型 ： \[ \begin{aligned} \min \quad & x_ 1 + x_ 2 + x_ 3 \\ \text{s.t.} \quad & x_ 1 + x_ 2 \ge 1 \quad \text{(边(1,2))} \\ & x_ 2 + x_ 3 \ge 1 \quad \text{(边(2,3))} \\ & x_ 1, x_ 2, x_ 3 \in \{0, 1\} \end{aligned} \] 这个整数规划的最优解显然是选择顶点2（即 \( x_ 2=1, x_ 1=x_ 3=0 \)），覆盖了两条边，总代价为1。所以 \( OPT_ {ILP} = 1 \)。 求解线性规划松弛 ： 将整数约束松弛为 \( x_ v \ge 0 \)。 \[ \begin{aligned} \min \quad & x_ 1 + x_ 2 + x_ 3 \\ \text{s.t.} \quad & x_ 1 + x_ 2 \ge 1 \\ & x_ 2 + x_ 3 \ge 1 \\ & x_ 1, x_ 2, x_ 3 \ge 0 \end{aligned} \] 我们可以用观察法求解。由于目标是最小化和，我们希望变量尽可能小，但必须满足约束。从对称性看，让 \( x_ 1 = x_ 3 = 0.5, x_ 2 = 0.5 \) 可以满足约束（因为 \( 0.5+0.5=1 \)），且目标值为 \( 0.5+0.5+0.5 = 1.5 \)。能否更小？如果 \( x_ 2 < 0.5 \)，那么为了满足第一条约束 \( x_ 1 + x_ 2 \ge 1 \)，必须有 \( x_ 1 > 0.5 \)；同理，为了满足第二条约束，必须有 \( x_ 3 > 0.5 \)。这样目标值至少为 \( x_ 1 + x_ 2 + x_ 3 > 0.5 + 0.5 + 0.5 = 1.5 \)。所以 \( x_ 1 = x_ 2 = x_ 3 = 0.5 \) 确实是最优解。因此，\( OPT_ {LP} = 1.5 \)。验证了 \( OPT_ {LP} \le OPT_ {ILP} \) 不成立？等等，这里 \( 1.5 > 1 \)，似乎矛盾？注意，是 \( OPT_ {LP} \le OPT_ {ILP} \) 吗？不对，因为LP是松弛，可行域比ILP大，其最优值应该 小于或等于 ILP的最优值。但这里 \( 1.5 > 1 \)。我检查一下：原ILP最优解是 \( x=(0,1,0) \)，目标值为1。这个解在LP中可行吗？可行，因为 \( 0,1,0 \) 都满足 \( \ge 0 \)。所以LP可行域包含这个整数解，那么LP的最优值应该 ≤ 1。为什么我算出来是1.5？因为 \( x=(0.5,0.5,0.5) \) 的目标值是1.5，比1大，说明它不是最优的。实际上，LP的另一个可行解是 \( x=(0,1,0) \)，目标值为1。那么 \( x=(0.5,0.5,0.5) \) 目标值1.5 > 1，所以它不是最优。真正的LP最优解是什么呢？考虑 \( x_ 2 \) 是关键。设 \( x_ 2 = a \)，则从第一个约束 \( x_ 1 \ge 1-a \)，第二个约束 \( x_ 3 \ge 1-a \)。目标函数为 \( x_ 1 + a + x_ 3 \ge (1-a) + a + (1-a) = 2 - a \)。我们要最小化，所以希望 \( a \) 尽量大。但 \( a \) 最大能为1（因为从整数解看）。如果 \( a=1 \)，那么 \( x_ 1 \ge 0, x_ 3 \ge 0 \)，取 \( x_ 1=x_ 3=0 \)，目标值为1。如果 \( a<1 \)，比如 \( a=0.8 \)，则 \( x_ 1 \ge 0.2, x_ 3 \ge 0.2 \)，目标值至少为 \( 0.2+0.8+0.2=1.2 > 1 \)。所以最优解确实是 \( a=1, x_ 1=x_ 3=0 \)，即 \( x=(0,1,0) \)，\( OPT_ {LP} = 1 \)。所以之前我误算了一个非最优的分数解。实际上，这个简单的图中，LP的最优解就是整数解。所以 \( OPT_ {LP} = OPT_ {ILP} = 1 \)。 应用贪心舍入算法 ： 求解LP得到最优解 \( x^* = (0, 1, 0) \)。 设定阈值 \( \theta = 0.5 \)。 舍入：因为 \( x_ 1^ =0 < 0.5 \)，舍为0；\( x_ 2^ =1 \ge 0.5 \)，舍为1；\( x_ 3^* =0 < 0.5 \)，舍为0。 得到顶点覆盖集合 \( S = \{2\} \)，大小 \( |S|=1 \)。这恰好是最优解。 第七步：更一般情况的说明 在上面的简单例子中，LP的最优解恰好是整数解，所以舍入后得到最优解。但在更复杂的图中，LP最优解通常是分数的。例如，考虑一个三角形（3个顶点的完全图 \( K_ 3 \)）。其ILP最优解是选择任意两个顶点（大小2），但LP最优解可以是 \( x_ v = 0.5 \) 对所有顶点，目标值为1.5。此时，舍入阈值0.5会将所有顶点都加入覆盖（因为 \( 0.5 \ge 0.5 \)），得到 \( |S|=3 \)，而最优解是2，近似比为 \( 3/2 = 1.5 \)，小于我们理论证明的上界2。这个算法在实践中通常能达到比2更好的近似比，但最坏情况（如某些二分图）可以达到2。 总结 在本示例中，我们针对NP-hard的最小顶点覆盖问题，介绍了从整数线性规划建模，到线性规划松弛，再到基于分数解的简单贪心舍入算法（阈值取0.5）的全过程。我们证明了该算法总能产生一个可行的顶点覆盖，并且其大小不超过最优解的2倍（即2-近似算法）。这个算法将困难的组合优化问题转化为可高效求解的线性规划，并通过简单的舍入获得有理论性能保证的近似解，是线性规划在近似算法中应用的典型范例。