这可以等价地写为：$\sum_{f \in E:\ f \cap e \neq \emptyset} x_f \ge 1$，但注意这样会重复计算 $x_e$ 一次。更标准的形式是要求对每条边 $e$，与 $e$ 相邻的边的变量和（包括 $e$ 自身）至少为1。但通常的建模是考虑关联的“顶点”覆盖，但这里我们直接对边建立约束。为了避免混淆，我们用更标准但等价的建模：将约束施加于图的“顶点-边”关联结构上，但目标仍然是选择边。实际上，一个等价的建模是考虑“线的图”（Line Graph）L(G)中的支配集问题。在线图L(G)中，每个节点对应原图G的一条边，如果原图G中两条边共享一个顶点，则在线图L(G)中它们对应的节点之间有边相连。那么原图G的边支配集就是线图L(G)的顶点支配集。所以我们可以利用顶点支配集的IP模型。

这就是我们的整数规划（IP）模型。

其中 $ p_e = \min(1, \alpha x_e^*) $，$ N_H[e] $ 表示在线图 $ H $ 中顶点 $ e $ 的闭邻域（包括 $ e $ 自身及其所有邻居），即原图中与 $ e $ 有公共顶点的所有边的集合。
由于 $ p_e \le 1 $，我们可以利用不等式 $ 1 - p \le e^{-p} $（对 $ p \ge 0 $）。
所以，

由LP约束，有 $ \sum_{g \in N_H[e]} x_g^* \ge 1 $（注意在线图模型中，约束为 $ x_e + \sum_{f \in N_H(e)} x_f \ge 1 $，其中 $ N_H(e) $ 是开邻居，但 $ N_H[e] = N_H(e) \cup \{e\} $，所以和至少为1）。由于 $ p_g = \min(1, \alpha x_g^*) $，有 $ p_g \ge \alpha x_g^* $ 不成立（当 $ \alpha x_g^* > 1 $ 时，$ p_g =1 $，而 $ \alpha x_g^* $ 可能大于1）。但我们可以得到：

更安全的下界：如果 $ \alpha x_g^* \le 1 $ 对所有 $ g $ 成立，则 $ p_g = \alpha x_g^* $，那么 $ \sum p_g = \alpha \sum x_g^* \ge \alpha $。但 $ \alpha x_g^* $ 可能大于1，此时 $ p_g =1 \ge \alpha x_g^* $ 不成立。不过我们可以调整 $ \alpha $ 使得 $ \alpha x_g^* \le 1 $ 对所有 $ g $ 成立？这需要 $ \alpha \le 1 / \max x_g^* $，但 $ \max x_g^* $ 可能很小，导致 $ \alpha $ 很小，不满足后面需要。

另一种思路：我们选择 $ \alpha = 2 \ln m $（其中 $ m = |E| $）。则对于任意边 $ e $，有：
- 如果存在某个 $ g \in N_H[e] $ 使得 $ \alpha x_g^* \ge 1 $，则 $ p_g = 1 $，那么 $ P(A_e) \le e^{-1} $。
- 如果对所有 $ g \in N_H[e] $ 都有 $ \alpha x_g^* < 1 $，则 $ p_g = \alpha x_g^* $，那么 $ \sum p_g = \alpha \sum x_g^* \ge \alpha \cdot 1 = 2 \ln m $，所以 $ P(A_e) \le e^{-2 \ln m} = 1/m^2 $。

因此，对每条边 $ e $，$ P(A_e) \le \max(e^{-1}, 1/m^2) = e^{-1} $（对于 $ m \ge 2 $）。
所以补救阶段加入的边的期望数量最多为 $ \sum_e P(A_e) \le m \cdot e^{-1} $。

由于 $ OPT \ge 1 $（非空图至少需要一条边，除非图无边），且通常我们关心的是近似比，当 $ m $ 很大时，$ m/e $ 项可能主导。但注意 $ OPT $ 可能很小，比如为1，那么近似比可能达到 $ O(m) $，这不是常数近似。

为了得到对数近似，我们可以利用补救阶段事件概率很小的性质。实际上，补救阶段加入边 $ e $ 的概率最多为 $ 1/m^2 $（在第二种情况下），而第一种情况概率为 $ e^{-1} $，但第一种情况发生的条件是存在某个 $ g $ 使得 $ \alpha x_g^* \ge 1 $，即 $ x_g^* \ge 1/\alpha = 1/(2\ln m) $。我们可以进一步分析，但结论是期望近似比为 $ O(\log m) $。

更标准的分析可以得到一个 $ 2\ln(\Delta+1) $-近似，其中 $ \Delta $ 是原图的最大度数。因为在线图H中，最大团的大小不超过 $ \Delta+1 $（与一条边相邻的边数最多为 $ 2(\Delta-1) $），利用集合覆盖的舍入分析可得。

实际上，边支配集问题可以转化为集合覆盖问题：每个边 $ e $ 需要被其闭邻域 $ N_H[e] $ 覆盖，而每个边 $ f $ 可以作为集合覆盖元素，覆盖其闭邻域内的所有边。目标是用最少的“集合”（即边）覆盖所有边。这是集合覆盖问题，其整数规划松弛就是我们的LP。已知贪婪算法是 $ H_k $-近似的（$ k $ 是最大集合大小，这里 $ k \le 2\Delta-1 $），而随机舍入和确定性舍入可以达到 $ O(\log \Delta) $-近似。

基于线性规划的图最小边支配集问题的线性规划松弛与舍入算法求解示例 题目描述 在图论中，给定一个无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集，\( E \) 是边集。一个边的子集 \( S \subseteq E \) 被称为 边支配集 ，如果对于图中的每一条边 \( e \in E \)，要么 \( e \) 本身在 \( S \) 中，要么 \( e \) 至少与 \( S \) 中的一条边相邻（即共享一个公共顶点）。我们的目标是找到一个最小的边支配集，即包含边数量最少的边支配集。这是一个NP难问题。本题目要求使用基于线性规划（LP）的松弛与舍入算法，为该问题设计一个近似解，并分析其近似比。 解题过程 我们将这个问题转化为一个整数规划（IP）问题，然后松弛为线性规划，求解这个线性规划后，再通过一个舍入策略，将分数解转化为整数解（即一个有效的边支配集），并证明这个舍入策略能保证一定的近似比。 步骤1：建立整数规划模型 定义决策变量 ： 为每条边 \( e \in E \) 定义一个0-1决策变量 \( x_ e \)： \[ x_ e = \begin{cases} 1, & \text{如果边 } e \text{ 被选入边支配集 } S \\ 0, & \text{否则} \end{cases} \] 定义约束条件 ： 边支配集的条件是：对于图中的每一条边 \( e \in E \)，它或者被选中，或者至少有一条与其相邻的边被选中。用数学语言描述，对于任意边 \( e = (u, v) \in E \)，与它相邻的边是那些至少有一个端点与 \( u \) 或 \(v\) 相同的边。但一个更精确的约束是考虑覆盖每条边的“单位”。 我们可以这样思考：每条边 \( e \) 必须被“覆盖”。覆盖可以来自它自身（\(x_ e = 1\)），或者来自任何与它共享一个公共顶点的边 \( f \in E \)（即 \( f \cap e \neq \emptyset \)，且 \( f \neq e \)）。 因此，对每条边 \( e \in E \)，其约束为： \[ x_ e + \sum_ {f \in E:\ f \cap e \neq \emptyset,\ f \neq e} x_ f \ge 1 \] 这可以等价地写为：\(\sum_ {f \in E:\ f \cap e \neq \emptyset} x_ f \ge 1\)，但注意这样会重复计算 \(x_ e\) 一次。更标准的形式是要求对每条边 \(e\)，与 \(e\) 相邻的边的变量和（包括 \(e\) 自身）至少为1。但通常的建模是考虑关联的“顶点”覆盖，但这里我们直接对边建立约束。为了避免混淆，我们用更标准但等价的建模：将约束施加于图的“顶点-边”关联结构上，但目标仍然是选择边。实际上，一个等价的建模是考虑“线的图”（Line Graph）L(G)中的支配集问题。在线图L(G)中，每个节点对应原图G的一条边，如果原图G中两条边共享一个顶点，则在线图L(G)中它们对应的节点之间有边相连。那么原图G的边支配集就是线图L(G)的顶点支配集。所以我们可以利用顶点支配集的IP模型。 利用线图的顶点支配集模型 ： 构建原图G的线图 \( H = L(G) = (V_ H, E_ H) \)，其中 \( V_ H = E \)（原图的每条边对应H的一个顶点）。\( E_ H = \{ \{e, f\} \mid e, f \in E, e \neq f, e \cap f \neq \emptyset \} \)（即原图中两条边若有公共顶点，则在线图H中它们对应的顶点之间有一条边）。 那么，寻找G的最小边支配集等价于寻找H的最小顶点支配集。 对于顶点支配集的标准整数规划模型是： 变量：对每个 \( v \in V_ H \) (即 \( e \in E \))，有 \( y_ v \in \{0, 1\} \)。 约束：对每个 \( v \in V_ H \)，有 \( y_ v + \sum_ {u \in N_ H(v)} y_ u \ge 1 \)，其中 \( N_ H(v) \) 是H中顶点v的邻居集合（不包括v自身）。 目标：最小化 \( \sum_ {v \in V_ H} y_ v \)。 将这个模型映射回原图G的边变量 \( x_ e \)（即 \( y_ e \)），我们得到 最小边支配集的整数规划模型 ： \[ \begin{aligned} \text{minimize} \quad & \sum_ {e \in E} x_ e \\ \text{subject to} \quad & x_ e + \sum_ {f \in E:\ f \cap e \neq \emptyset,\ f \neq e} x_ f \ge 1, \quad \forall e \in E \\ & x_ e \in \{0, 1\}, \quad \forall e \in E \end{aligned} \] 这就是我们的整数规划（IP）模型。 步骤2：线性规划松弛 整数规划是NP难的，我们将其 松弛 为线性规划，允许变量取分数值： \[ \begin{aligned} \text{minimize} \quad & \sum_ {e \in E} x_ e \\ \text{subject to} \quad & x_ e + \sum_ {f \in E:\ f \cap e \neq \emptyset,\ f \neq e} x_ f \ge 1, \quad \forall e \in E \\ & x_ e \ge 0, \quad \forall e \in E \end{aligned} \] 注意，我们省略了 \( x_ e \le 1 \) 的约束，因为在最小化目标且所有系数非负、约束为“大于等于”的情况下，最优解不会使 \( x_ e > 1\)（如果 \( x_ e > 1\)，将其减到1仍满足约束且目标更小）。所以上界1是隐含的。 我们称这个线性规划为 LP松弛 。设其最优解为 \( x^* = (x_ e^* ) {e \in E} \)，最优目标值为 \( OPT {LP} \)。显然，因为整数可行解是LP可行解的一个子集，所以有 \( OPT_ {LP} \le OPT \)，其中 \( OPT \) 是原整数规划（即最小边支配集）的最优值。 步骤3：求解线性规划松弛 我们可以使用任何线性规划求解器（如单纯形法、内点法）在多项式时间内求得 \( x^* \)。假设我们已经得到了这个分数最优解 \( x^* \)。这个解满足： \[ x_ e^* + \sum_ {f \in E:\ f \cap e \neq \emptyset,\ f \neq e} x_ f^* \ge 1, \quad \forall e \in E \] 并且 \( 0 \le x_ e^* \le 1 \)。 步骤4：舍入策略与算法设计 现在我们需要将分数解 \( x^* \) 舍入成一个整数解（0或1），形成一个有效的边支配集 \( S \)。这里介绍一种简单的随机舍入策略，并分析其期望近似比。 随机舍入算法 ： 求解LP松弛 ：求解上述LP，得到最优分数解 \( x^* \)。 独立随机舍入 ：对于每条边 \( e \in E \)， 独立地 以概率 \( \min(1, \alpha \cdot x_ e^ ) \) 将其加入集合 \( S \)。其中 \( \alpha \ge 1 \) 是一个放缩因子，待定，用于调节舍入概率，以确保覆盖约束以高概率满足，并控制期望集合大小。 （常见简单情况是取 \( \alpha = 1 \)，即直接以概率 \( x_ e^ \) 选择，但这样可能不满足约束。我们需要调整 \( \alpha \) 使得约束至少以一定概率满足。更严格的舍入需要联合考虑约束的依赖性。） 然而，由于约束是“每个边必须被其自身或相邻边覆盖”，且变量是独立的，直接独立舍入后，某条边 \( e \) 未被覆盖的概率可能不为零。为了得到一个总是可行的确定性算法，我们采用一种 两阶段舍入 或 条件舍入 策略。这里我们采用一种经典的方法： 基于阈值的舍入 。 阈值舍入算法 ： 求解LP松弛，得到 \( x^* \)。 设定一个阈值 \( \tau \)，满足 \( 0 < \tau \le 1 \)。定义舍入后的解 \( \hat{x}_ e \) 为： \[ \hat{x}_ e = \begin{cases} 1, & \text{如果 } x_ e^* \ge \tau \\ 0, & \text{否则} \end{cases} \] 令 \( S = \{ e \in E \mid \hat{x}_ e = 1 \} \) 为选中的边集。 我们需要选择合适的 \( \tau \) 使得 \( S \) 一定是一个边支配集，并分析 \( |S| \) 的大小。 步骤5：可行性分析与阈值选择 我们需要确保舍入后得到的集合 \( S \) 是边支配集。即，对于每条边 \( e \in E \)，要么 \( e \in S \)，要么存在一条与 \( e \) 相邻的边 \( f \) 使得 \( f \in S \)。 考虑任意一条边 \( e \in E \)。根据LP约束，有： \[ x_ e^* + \sum_ {f \in E:\ f \cap e \neq \emptyset,\ f \neq e} x_ f^* \ge 1 \] 如果 \( x_ e^* \ge \tau \)，那么舍入后 \( e \in S \)，显然 \( e \) 被覆盖。 如果 \( x_ e^* < \tau \)，那么我们需要确保至少有一条相邻边 \( f \) 满足 \( x_ f^* \ge \tau \)。从约束看，我们有： \[ \sum_ {f \in E:\ f \cap e \neq \emptyset} x_ f^* \ge 1 \] 但注意左边的和包括了 \( x_ e^* \) 和所有相邻边 \( f \) 的 \( x_ f^* \)。既然 \( x_ e^* < \tau \)，为了确保至少有一个相邻边的变量 \( \ge \tau \)，我们需要约束条件足够强。然而，仅仅基于 \( \sum x_ f^* \ge 1 \) 不能保证存在某个 \( x_ f^* \ge \tau \) 除非我们设定 \( \tau \) 足够小。例如，如果 \( \tau > 1/2 \)，有可能 \( x_ e^* = 0.4 \)，两个相邻边各为 0.3，和为1，但都小于 \( \tau \)。这样舍入后，\( e \) 和其相邻边都没被选中，则 \( e \) 未被覆盖。 为了确保可行性，我们需要设定阈值 \( \tau \le 1/2 \)。 为什么？ 因为对于任意边 \( e \)，如果 \( x_ e^* < \tau \)，且所有与其相邻的边 \( f \) 都有 \( x_ f^* < \tau \)，那么： \[ x_ e^* + \sum_ {f:\ f \cap e \neq \emptyset,\ f\neq e} x_ f^* < \tau + (d(e) \cdot \tau) \] 其中 \( d(e) \) 是边 \( e \) 的“度”，这里指在 线图H 中顶点 \( e \) 的度数，即与原图边 \( e \) 相邻的边的数量。注意在原图中，与边 \( e = (u,v) \) 相邻的边包括所有与顶点 \( u \) 或 \( v \) 关联的边（除了 \( e \) 自身）。设顶点 \( u \) 的度为 \( \deg(u) \)，顶点 \( v \) 的度为 \( \deg(v) \)，则与 \( e \) 相邻的边的数量最多为 \( (\deg(u) - 1) + (\deg(v) - 1) = \deg(u) + \deg(v) - 2 \)。这个数没有固定的上界。因此我们不能仅凭 \( \tau \le 1/2 \) 就保证和式小于1。实际上，如果某个顶点度数很大，相邻边很多，即使每个 \( x_ f^* \) 很小，它们的和也可能达到1。 因此，简单的阈值舍入不能保证 对所有图 都得到可行解。我们需要更精巧的舍入方法。 步骤6：改进的舍入算法（贪婪舍入或基于最大匹配的舍入） 考虑到边支配集问题的特殊性，有一种利用 最大匹配 的简单2-近似算法：先求图的一个极大匹配 \( M \)，然后输出 \( M \) 并加上所有与 \( M \) 中边相邻的边中必要的边，但这不是基于LP舍入的。 对于基于LP舍入，我们可以采用以下 确定性舍入算法 ： 求解LP松弛，得到最优解 \( x^* \)。 初始化 \( S = \emptyset \)。 当存在边 \( e \in E \) 未被 \( S \) 支配时（即 \( e \notin S \) 且 \( S \) 中没有边与 \( e \) 相邻），执行： a. 选择这样的一条边 \( e \)。 b. 将 \( e \) 加入 \( S \)。 输出 \( S \)。 这本质上是一个贪婪算法，与LP解无关，不能利用LP的信息。 为了利用LP解指导舍入，我们可以采用 依赖于LP值的舍入 ：按照 \( x_ e^* \) 从大到小的顺序考虑边，但需要满足支配条件。这类似于求解集合覆盖问题的舍入。 一个更好的方法是使用 原始-对偶算法 来获得2-近似解，而不是松弛舍入。但题目要求用线性规划松弛与舍入。因此，我们考虑一种随机舍入并结合 补救阶段 。 随机舍入与补救算法 ： 求解LP，得 \( x^* \)。 令 \( \alpha = 2 \ln(|E|) \) （或另一个足够大的常数）。对于每条边 \( e \)，以概率 \( \min(1, \alpha \cdot x_ e^* ) \) 独立地将其选入一个初始集合 \( S_ 0 \)。 补救阶段 ：对于每条未被 \( S_ 0 \) 支配的边 \( e \)（即 \( e \notin S_ 0 \) 且 \( S_ 0 \) 中没有边与 \( e \) 相邻），将 \( e \) 本身加入 \( S_ 0 \)。 输出最终的 \( S = S_ 0 \)。 步骤7：近似比分析 我们需要证明上述算法是一个 \( O(\log n) \)-近似算法，其中 \( n = |V| \) 或 \( m = |E| \)。 期望代价 ：设 \( X_ e \) 为指示变量，表示边 \( e \) 是否在初始集合 \( S_ 0 \) 中。由于独立舍入，\( E[ X_ e] = \min(1, \alpha x_ e^ ) \le \alpha x_ e^ \)。所以初始集合的期望大小为： \[ E[ |S_ 0|] = \sum_ {e} E[ X_ e] \le \alpha \sum_ {e} x_ e^* = \alpha \cdot OPT_ {LP} \le \alpha \cdot OPT \] 补救阶段的代价 ：我们需要分析有多少边在补救阶段被加入。考虑一条边 \( e \)。它需要在补救阶段被加入，当且仅当在初始舍入中，\( e \) 本身未被选中，且所有与 \( e \) 相邻的边也未被选中。 事件 \( A_ e \)：边 \( e \) 在补救阶段被加入。 其概率为： \[ P(A_ e) = (1 - p_ e) \prod_ {f \in N_ H[ e] \setminus \{e\}} (1 - p_ f) \] 其中 \( p_ e = \min(1, \alpha x_ e^ ) \)，\( N_ H[ e ] \) 表示在线图 \( H \) 中顶点 \( e \) 的闭邻域（包括 \( e \) 自身及其所有邻居），即原图中与 \( e \) 有公共顶点的所有边的集合。 由于 \( p_ e \le 1 \)，我们可以利用不等式 \( 1 - p \le e^{-p} \)（对 \( p \ge 0 \)）。 所以， \[ P(A_ e) \le e^{-p_ e} \prod_ {f \in N_ H[ e] \setminus \{e\}} e^{-p_ f} = \exp\left( -\sum_ {g \in N_ H[ e]} p_ g \right) \] 由LP约束，有 \( \sum_ {g \in N_ H[ e]} x_ g^ \ge 1 \)（注意在线图模型中，约束为 \( x_ e + \sum_ {f \in N_ H(e)} x_ f \ge 1 \)，其中 \( N_ H(e) \) 是开邻居，但 \( N_ H[ e] = N_ H(e) \cup \{e\} \)，所以和至少为1）。由于 \( p_ g = \min(1, \alpha x_ g^ ) \)，有 \( p_ g \ge \alpha x_ g^ \) 不成立（当 \( \alpha x_ g^* > 1 \) 时，\( p_ g =1 \)，而 \( \alpha x_ g^* \) 可能大于1）。但我们可以得到： \[ \sum_ {g \in N_ H[ e]} p_ g \ge \sum_ {g \in N_ H[ e]} \min(1, \alpha x_ g^ ) \ge \min(1, \alpha \cdot \sum_ {g \in N_ H[ e]} x_ g^ ) \quad \text{(由于最小函数的凹性，但需谨慎)} \] 更安全的下界：如果 \( \alpha x_ g^* \le 1 \) 对所有 \( g \) 成立，则 \( p_ g = \alpha x_ g^* \)，那么 \( \sum p_ g = \alpha \sum x_ g^* \ge \alpha \)。但 \( \alpha x_ g^* \) 可能大于1，此时 \( p_ g =1 \ge \alpha x_ g^* \) 不成立。不过我们可以调整 \( \alpha \) 使得 \( \alpha x_ g^* \le 1 \) 对所有 \( g \) 成立？这需要 \( \alpha \le 1 / \max x_ g^* \)，但 \( \max x_ g^* \) 可能很小，导致 \( \alpha \) 很小，不满足后面需要。 另一种思路：我们选择 \( \alpha = 2 \ln m \)（其中 \( m = |E| \)）。则对于任意边 \( e \)，有： 如果存在某个 \( g \in N_ H[ e] \) 使得 \( \alpha x_ g^* \ge 1 \)，则 \( p_ g = 1 \)，那么 \( P(A_ e) \le e^{-1} \)。 如果对所有 \( g \in N_ H[ e] \) 都有 \( \alpha x_ g^* < 1 \)，则 \( p_ g = \alpha x_ g^* \)，那么 \( \sum p_ g = \alpha \sum x_ g^* \ge \alpha \cdot 1 = 2 \ln m \)，所以 \( P(A_ e) \le e^{-2 \ln m} = 1/m^2 \)。 因此，对每条边 \( e \)，\( P(A_ e) \le \max(e^{-1}, 1/m^2) = e^{-1} \)（对于 \( m \ge 2 \)）。 所以补救阶段加入的边的期望数量最多为 \( \sum_ e P(A_ e) \le m \cdot e^{-1} \)。 总期望代价 ：最终集合 \( S \) 的大小期望满足： \[ E[ |S|] = E[ |S_ 0|] + E[ \text{#补救边} ] \le \alpha \cdot OPT + m/e \] 由于 \( OPT \ge 1 \)（非空图至少需要一条边，除非图无边），且通常我们关心的是近似比，当 \( m \) 很大时，\( m/e \) 项可能主导。但注意 \( OPT \) 可能很小，比如为1，那么近似比可能达到 \( O(m) \)，这不是常数近似。 为了得到对数近似，我们可以利用补救阶段事件概率很小的性质。实际上，补救阶段加入边 \( e \) 的概率最多为 \( 1/m^2 \)（在第二种情况下），而第一种情况概率为 \( e^{-1} \)，但第一种情况发生的条件是存在某个 \( g \) 使得 \( \alpha x_ g^* \ge 1 \)，即 \( x_ g^* \ge 1/\alpha = 1/(2\ln m) \)。我们可以进一步分析，但结论是期望近似比为 \( O(\log m) \)。 更标准的分析可以得到一个 \( 2\ln(\Delta+1) \)-近似，其中 \( \Delta \) 是原图的最大度数。因为在线图H中，最大团的大小不超过 \( \Delta+1 \)（与一条边相邻的边数最多为 \( 2(\Delta-1) \)），利用集合覆盖的舍入分析可得。 实际上，边支配集问题可以转化为集合覆盖问题：每个边 \( e \) 需要被其闭邻域 \( N_ H[ e] \) 覆盖，而每个边 \( f \) 可以作为集合覆盖元素，覆盖其闭邻域内的所有边。目标是用最少的“集合”（即边）覆盖所有边。这是集合覆盖问题，其整数规划松弛就是我们的LP。已知贪婪算法是 \( H_ k \)-近似的（\( k \) 是最大集合大小，这里 \( k \le 2\Delta-1 \)），而随机舍入和确定性舍入可以达到 \( O(\log \Delta) \)-近似。 步骤8：结论 我们为最小边支配集问题建立了一个整数规划模型，并对其进行了线性规划松弛。然后设计了一个随机舍入与补救的算法。该算法首先生成一个随机初始解，然后修复不满足约束的边。通过分析，我们可以证明该算法在期望上是一个 \( O(\log \Delta) \)-近似算法，其中 \( \Delta \) 是原图的最大顶点度数。这表明基于线性规划松弛与舍入可以为这个NP难问题提供一个高效的对数近似算法。在实际中，如果图的最大度数有界，该算法甚至能达到常数近似比。