基于线性规划的图最小顶点覆盖问题的半定规划松弛与舍入算法求解示例
字数 7178 2025-12-07 10:28:16

基于线性规划的图最小顶点覆盖问题的半定规划松弛与舍入算法求解示例

1. 问题描述

我们考虑一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集，包含 \(n\) 个顶点，\(E\) 是边集，包含 \(m\) 条边。一个顶点覆盖 (Vertex Cover) 是顶点集 \(V\) 的一个子集 \(S \subseteq V\)，使得图 \(G\) 中的每条边至少有一个端点属于 \(S\)。最小顶点覆盖问题 (Minimum Vertex Cover Problem, MVC) 的目标是找到一个顶点数最少的顶点覆盖。这是一个经典的NP难组合优化问题。

传统的线性规划松弛（为每个顶点 \(i\) 引入变量 \(x_i \in \{0, 1\}\)，表示顶点是否在覆盖集中）及其舍入是常见的近似算法。本示例将介绍一个更高级的松弛方法：半定规划松弛 (Semidefinite Programming Relaxation)，并结合随机舍入算法，给出一个性能保证更好的近似解。

2. 数学模型构建

2.1 整数规划模型

标准0-1整数规划模型：

  • 决策变量：对每个顶点 \(i \in V\)，令 \(x_i = 1\) 表示顶点 \(i\) 在覆盖集中，\(x_i = 0\) 表示不在。
  • 目标：最小化覆盖集的大小，即 \(\min \sum_{i \in V} x_i\)。
  • 约束：对于每条边 \((i, j) \in E\)，至少有一个端点被选中，即 \(x_i + x_j \ge 1\)。
  • 变量类型：\(x_i \in \{0, 1\}\)。

2.2 半定规划松弛

半定规划是对线性规划的推广，允许变量为半正定矩阵。我们将 \(x_i \in \{0, 1\}\) 映射到向量空间。

  • 步骤1：向量编码
    为每个顶点 \(i\) 关联一个 \(n+1\) 维的单位向量 \(\mathbf{v}_i \in \mathbb{R}^{n+1}\)，满足 \(\|\mathbf{v}_i\| = 1\)。同时，引入一个特殊的单位向量 \(\mathbf{v}_0\)，用于表示“状态”。
    我们定义一种特殊的对应关系：

    • 如果 \(x_i = 1\)（顶点在覆盖集中），我们希望 \(\mathbf{v}_i\) 与 \(\mathbf{v}_0\) 的方向“相同”，即点积 \(\mathbf{v}_i \cdot \mathbf{v}_0\) 较大（理想为1）。
    • 如果 \(x_i = 0\)（顶点不在覆盖集中），我们希望 \(\mathbf{v}_i\) 与 \(\mathbf{v}_0\) 的方向“相反”，即点积 \(\mathbf{v}_i \cdot \mathbf{v}_0\) 较小（理想为-1）。
      一种巧妙的建模是引入新的变量 \(y_i\)，使得 \(x_i = (1 - \mathbf{v}_0 \cdot \mathbf{v}_i) / 2\)。当 \(\mathbf{v}_i\) 与 \(\mathbf{v}_0\) 同向时，\(x_i \approx 0\)；反向时，\(x_i \approx 1\)。但更常见的一种等价且对称的形式是Max-Cut风格的松弛。

  • 步骤2：重新表述约束
    考虑原约束 \(x_i + x_j \ge 1\)。利用上述关系 \(x_i = (1 - \mathbf{v}_0 \cdot \mathbf{v}_i) / 2\)，代入得：
    \((1 - \mathbf{v}_0 \cdot \mathbf{v}_i)/2 + (1 - \mathbf{v}_0 \cdot \mathbf{v}_j)/2 \ge 1\)。
    简化后得到：\(\mathbf{v}_0 \cdot \mathbf{v}_i + \mathbf{v}_0 \cdot \mathbf{v}_j \le 0\)。
    这个约束表达了两件事：如果一条边的两个端点都不在覆盖中（即都希望与 \(\mathbf{v}_0\) 同向，点积为正），那么这个约束 \(\le 0\) 将被违反。为了满足它，至少有一个端点对应的向量必须与 \(\mathbf{v}_0\) 不“太同向”。

  • 步骤3：半定规划模型 (SDP Relaxation)
    我们引入一个半正定矩阵 \(Y\)，其元素 \(y_{ij} = \mathbf{v}_i \cdot \mathbf{v}_j\)（包括 \(i, j\) 从0到 \(n\)）。这个矩阵 \(Y\) 是半正定的（记为 \(Y \succeq 0\)），并且对角线元素 \(y_{ii} = 1\)（因为向量是单位向量）。
    目标函数 \(\sum_i x_i = \sum_i (1 - y_{0i})/2\)。
    约束 \(\mathbf{v}_0 \cdot \mathbf{v}_i + \mathbf{v}_0 \cdot \mathbf{v}_j \le 0\) 变为 \(y_{0i} + y_{0j} \le 0\)。
    我们得到如下半定规划松弛模型：

\[ \begin{aligned} \min \quad & \frac{1}{2} \sum_{i=1}^{n} (1 - y_{0i}) \\ \text{s.t.} \quad & y_{0i} + y_{0j} \le 0, \quad \forall (i, j) \in E, \\ & y_{ii} = 1, \quad \forall i = 0, 1, ..., n, \\ & Y \succeq 0. \end{aligned} \]

这个模型是原整数规划问题的松弛，因为原问题的任意可行解（0-1向量）都可以构造出满足上述SDP约束的解（通过将 $ \mathbf{v}_0 $ 设为某个单位向量，$ \mathbf{v}_i = \mathbf{v}_0 $ 若 $ x_i=0 $，或 $ \mathbf{v}_i = -\mathbf{v}_0 $ 若 $ x_i=1 $，但注意这会导致 $ y_{0i} = \pm 1 $，而 $ x_i = (1 - y_{0i})/2 $ 给出了正确的01值，并且边约束被满足）。因此，SDP的最优值不大于原整数规划的最优值。

3. 算法步骤：求解与舍入

3.1 求解半定规划
我们可以使用内点法（如SeDuMi, SDPT3等求解器）来求解上述半定规划模型，得到最优的半正定矩阵 \(Y^*\) 和最优目标值 \(OPT_{SDP}\)。由于 \(Y^*\) 是半正定的，我们可以通过Cholesky分解或特征值分解得到一个向量配置 \(\{\mathbf{v}_0^*, \mathbf{v}_1^*, ..., \mathbf{v}_n^*\}\)，满足 \(y_{ij}^* = \mathbf{v}_i^* \cdot \mathbf{v}_j^*\)。这些向量位于一个（至多）\(n+1\) 维的单位球面上。

3.2 随机超平面舍入 (Randomized Hyperplane Rounding)
这是从连续向量解得到离散顶点覆盖的关键步骤。其思想来源于Goemans-Williamson MAX-CUT算法的舍入技术。

  1. 随机选取法向量：在 \(n+1\) 维的单位球面上，均匀随机地选取一个单位向量 \(\mathbf{r}\)。
  2. 划分顶点：定义顶点覆盖 \(S\) 为满足 \(\mathbf{v}_0^* \cdot \mathbf{v}_i^* \ge \mathbf{r} \cdot \mathbf{v}_i^*\) 的顶点 \(i\) 的集合。一个等价的、更直观的几何操作是：考虑由法向量 \(\mathbf{r}\) 定义的随机超平面 \(H: \{ \mathbf{x} | \mathbf{r} \cdot \mathbf{x} = 0 \}\)。这个超平面将球面分成两个半球。我们将顶点 \(i\) 放入覆盖集 \(S\) 当且仅当向量 \(\mathbf{v}_i^*\) 和 \(\mathbf{v}_0^*\) 落在该随机超平面的同一侧。即，如果 \(\text{sign}(\mathbf{r} \cdot \mathbf{v}_i^*) = \text{sign}(\mathbf{r} \cdot \mathbf{v}_0^*)\)，则 \(i \in S\)。否则 \(i \notin S\)。
  3. 可行性修正：经过上述舍入得到的集合 \(S\) 不一定是一个合法的顶点覆盖。因为有可能某条边 \((i, j)\) 的两个端点 \(\mathbf{v}_i^*\) 和 \(\mathbf{v}_j^*\) 都恰好与 \(\mathbf{v}_0^*\) 位于超平面异侧，从而均未被选中。但是，我们可以证明对于每条边 \((i, j)\)，其两个端点都被舍入为“不在覆盖中”的概率是有限的。为了得到一个必然可行的解，我们采用以下策略：在舍入后，检查所有边。对于任何一条两个端点都不在 \(S\) 中的边，我们将其任意一个端点（例如编号较小的那个）加入 \(S\)。这一步保证了最终集合 \(S\) 是一个顶点覆盖。

4. 理论近似比分析

我们可以分析这个算法的期望近似比。

  • 单顶点舍入概率：对于一个顶点 \(i\)，其被舍入到覆盖集 \(S\) 的概率（在修正前）等于其向量 \(\mathbf{v}_i^*\) 与参考向量 \(\mathbf{v}_0^*\) 落在随机超平面同一侧的概率。在球面对称性下，这个概率等于 \(1 - \frac{\theta_{0i}}{\pi}\)，其中 \(\theta_{0i} = \arccos(y_{0i}^*)\) 是向量 \(\mathbf{v}_0^*\) 和 \(\mathbf{v}_i^*\) 之间的夹角。因此，\(P(i \in S_{\text{initial}}) = 1 - \frac{\arccos(y_{0i}^*)}{\pi}\)。
  • 目标函数期望：初始覆盖集的期望大小为 \(E[|S_{\text{initial}}|] = \sum_{i=1}^n \left(1 - \frac{\arccos(y_{0i}^*)}{\pi} \right)\)。
  • 与SDP目标的关系：SDP的目标是 \(OPT_{SDP} = \frac{1}{2} \sum_{i=1}^n (1 - y_{0i}^*)\)。
    可以证明，对于 \(y \in [-1, 1]\)，存在一个函数 \(\alpha \approx 1.114\)（更精确地，\(\alpha = 2 / (1 - \cos(\pi/4))\) 在特定的GW分析中出现，但对于顶点覆盖，经典的Karant 分析给出近似比2），使得 \(1 - \frac{\arccos(y)}{\pi} \le \alpha \cdot \frac{1}{2}(1 - y)\)。
    因此，\(E[|S_{\text{initial}}|] \le \alpha \cdot OPT_{SDP} \le \alpha \cdot OPT_{IP}\)，其中 \(OPT_{IP}\) 是原整数规划最优值。
  • 可行性修正的成本：需要分析因为添加边端点而额外增加的顶点数期望。对于一条边 \((i, j)\)，其两个端点初始都不在 \(S\) 中的概率是 \(\frac{\theta_{ij}}{\pi}\)，其中 \(\theta_{ij} = \arccos(y_{ij}^*)\)。由SDP约束 \(y_{0i}^* + y_{0j}^* \le 0\) 和球面几何，可以推导出 \(\theta_{ij} \ge \pi/2\)，从而 \(\frac{\theta_{ij}}{\pi} \ge 1/2\)。然而，在修正时，我们只添加一个端点。通过更精细的概率分析（考虑每条边被修正的概率及其对期望大小的贡献），结合SDP约束，可以证明最终得到的覆盖集 \(S\) 的期望大小满足 \(E[|S|] \le 2 \cdot OPT_{SDP} \le 2 \cdot OPT_{IP}\)。
    这就是著名的基于SDP松弛的随机舍入算法对于最小顶点覆盖问题的2-近似算法。虽然期望近似比是2，但通过多次运行随机舍入并取最小的可行解，可以以高概率得到接近2倍最优解的解。

5. 一个简单算例

考虑一个三角形图（3个顶点，3条边）：\(V = \{1,2,3\}\), \(E = \{(1,2), (2,3), (1,3)\}\)。最小顶点覆盖大小为2（任意两个顶点即可）。

  • 构建并求解SDP：
    变量：\(y_{01}, y_{02}, y_{03}, y_{12}, y_{13}, y_{23}\)。
    目标：\(\min \frac{1}{2}[(1-y_{01}) + (1-y_{02}) + (1-y_{03})]\)。
    约束：

    1. \(y_{01} + y_{02} \le 0\)
    2. \(y_{02} + y_{03} \le 0\)
    3. \(y_{01} + y_{03} \le 0\)
    4. \(y_{00}=y_{11}=y_{22}=y_{33}=1\)
    5. \(Y = \begin{bmatrix} 1 & y_{01} & y_{02} & y_{03} \\ y_{01} & 1 & y_{12} & y_{13} \\ y_{02} & y_{12} & 1 & y_{23} \\ y_{03} & y_{13} & y_{23} & 1 \end{bmatrix} \succeq 0\)

    一个最优解可以通过对称性猜测：\(y_{01}^* = y_{02}^* = y_{03}^* = -\frac{1}{3}\)，并且 \(y_{12}^* = y_{13}^* = y_{23}^* = \frac{1}{3}\)（可以验证矩阵 \(Y\) 是半正定的）。此时SDP目标值 = \(\frac{1}{2}[ (1+\frac{1}{3}) \times 3] = 2\)。恰好等于整数最优解。

  • 向量构造：
    我们可以找到一个4维向量配置（\(n+1=4\)）来实现这个 \(Y^*\)（例如，通过特征值分解）。向量间夹角满足 \(\cos\theta_{0i} = -\frac{1}{3}\)。

  • 随机舍入：
    随机选取超平面法向量 \(\mathbf{r}\)。对于每个顶点 \(i\)，判断 \(\mathbf{v}_i^*\) 是否与 \(\mathbf{v}_0^*\) 在 \(\mathbf{r}\) 定义的超平面同侧。
    由于对称性，每个顶点被选入初始覆盖集的概率为 \(1 - \frac{\arccos(-1/3)}{\pi} \approx 1 - (1.9106 / \pi) \approx 1 - 0.6082 = 0.3918\)。
    初始覆盖集大小的期望约为 \(3 \times 0.3918 = 1.1754 < 2\)。
    但此时初始集很可能不是可行覆盖（例如，三条边可能都没有被覆盖）。进行可行性修正：检查所有边，将未被覆盖的边的某个端点加入。由于图很小，可以枚举情况。最终得到的覆盖集大小期望值会上升到2，与理论分析的2倍近似比一致。实际上，由于SDP目标值已经是2，任何可行覆盖的大小至少是2，而我们的算法期望产出大小为2的覆盖，这表明对于这个例子，算法是期望最优的。

6. 总结

本示例介绍了求解最小顶点覆盖问题的一种高级方法：

  1. 建立半定规划松弛模型，将0-1变量松弛为高维球面上的向量。
  2. 求解SDP得到最优向量配置。
  3. 使用随机超平面舍入，将连续向量解转化为离散的顶点子集。
  4. 进行简单的可行性修正，确保结果是一个顶点覆盖。
    该方法提供了期望下的2-近似保证，是经典线性规划舍入（也是2-近似）的一个有趣替代，有时在实践中能获得更好的经验性能。此方法展示了如何将组合优化问题嵌入连续向量空间，并利用几何概率工具进行分析和设计算法。
基于线性规划的图最小顶点覆盖问题的半定规划松弛与舍入算法求解示例 1. 问题描述 我们考虑一个无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集，包含 \( n \) 个顶点，\( E \) 是边集，包含 \( m \) 条边。一个顶点覆盖 (Vertex Cover) 是顶点集 \( V \) 的一个子集 \( S \subseteq V \)，使得图 \( G \) 中的每条边至少有一个端点属于 \( S \)。 最小顶点覆盖问题 (Minimum Vertex Cover Problem, MVC) 的目标是找到一个顶点数最少的顶点覆盖。这是一个经典的NP难组合优化问题。 传统的线性规划松弛（为每个顶点 \( i \) 引入变量 \( x_ i \in \{0, 1\} \)，表示顶点是否在覆盖集中）及其舍入是常见的近似算法。本示例将介绍一个更高级的松弛方法： 半定规划松弛 (Semidefinite Programming Relaxation) ，并结合随机舍入算法，给出一个性能保证更好的近似解。 2. 数学模型构建 2.1 整数规划模型 标准0-1整数规划模型： 决策变量：对每个顶点 \( i \in V \)，令 \( x_ i = 1 \) 表示顶点 \( i \) 在覆盖集中，\( x_ i = 0 \) 表示不在。 目标：最小化覆盖集的大小，即 \( \min \sum_ {i \in V} x_ i \)。 约束：对于每条边 \( (i, j) \in E \)，至少有一个端点被选中，即 \( x_ i + x_ j \ge 1 \)。 变量类型：\( x_ i \in \{0, 1\} \)。 2.2 半定规划松弛 半定规划是对线性规划的推广，允许变量为半正定矩阵。我们将 \( x_ i \in \{0, 1\} \) 映射到向量空间。 步骤1：向量编码 为每个顶点 \( i \) 关联一个 \( n+1 \) 维的单位向量 \( \mathbf{v}_ i \in \mathbb{R}^{n+1} \)，满足 \( \|\mathbf{v}_ i\| = 1 \)。同时，引入一个特殊的单位向量 \( \mathbf{v}_ 0 \)，用于表示“状态”。 我们定义一种特殊的对应关系： 如果 \( x_ i = 1 \)（顶点在覆盖集中），我们希望 \( \mathbf{v}_ i \) 与 \( \mathbf{v}_ 0 \) 的方向“相同”，即点积 \( \mathbf{v}_ i \cdot \mathbf{v}_ 0 \) 较大（理想为1）。 如果 \( x_ i = 0 \)（顶点不在覆盖集中），我们希望 \( \mathbf{v}_ i \) 与 \( \mathbf{v}_ 0 \) 的方向“相反”，即点积 \( \mathbf{v}_ i \cdot \mathbf{v}_ 0 \) 较小（理想为-1）。 一种巧妙的建模是引入新的变量 \( y_ i \)，使得 \( x_ i = (1 - \mathbf{v}_ 0 \cdot \mathbf{v}_ i) / 2 \)。当 \( \mathbf{v}_ i \) 与 \( \mathbf{v}_ 0 \) 同向时，\( x_ i \approx 0 \)；反向时，\( x_ i \approx 1 \)。但更常见的一种等价且对称的形式是 Max-Cut 风格的松弛。 步骤2：重新表述约束 考虑原约束 \( x_ i + x_ j \ge 1 \)。利用上述关系 \( x_ i = (1 - \mathbf{v}_ 0 \cdot \mathbf{v}_ i) / 2 \)，代入得： \( (1 - \mathbf{v}_ 0 \cdot \mathbf{v}_ i)/2 + (1 - \mathbf{v}_ 0 \cdot \mathbf{v}_ j)/2 \ge 1 \)。 简化后得到：\( \mathbf{v}_ 0 \cdot \mathbf{v}_ i + \mathbf{v}_ 0 \cdot \mathbf{v}_ j \le 0 \)。 这个约束表达了两件事：如果一条边的两个端点都不在覆盖中（即都希望与 \( \mathbf{v}_ 0 \) 同向，点积为正），那么这个约束 \( \le 0 \) 将被违反。为了满足它，至少有一个端点对应的向量必须与 \( \mathbf{v}_ 0 \) 不“太同向”。 步骤3：半定规划模型 (SDP Relaxation) 我们引入一个半正定矩阵 \( Y \)，其元素 \( y_ {ij} = \mathbf{v} i \cdot \mathbf{v} j \)（包括 \( i, j \) 从0到 \( n \)）。这个矩阵 \( Y \) 是半正定的（记为 \( Y \succeq 0 \)），并且对角线元素 \( y {ii} = 1 \)（因为向量是单位向量）。 目标函数 \( \sum_ i x_ i = \sum_ i (1 - y {0i})/2 \)。 约束 \( \mathbf{v} 0 \cdot \mathbf{v} i + \mathbf{v} 0 \cdot \mathbf{v} j \le 0 \) 变为 \( y {0i} + y {0j} \le 0 \)。 我们得到如下半定规划松弛模型： \[ \begin{aligned} \min \quad & \frac{1}{2} \sum {i=1}^{n} (1 - y {0i}) \\ \text{s.t.} \quad & y_ {0i} + y_ {0j} \le 0, \quad \forall (i, j) \in E, \\ & y_ {ii} = 1, \quad \forall i = 0, 1, ..., n, \\ & Y \succeq 0. \end{aligned} \] 这个模型是原整数规划问题的松弛，因为原问题的任意可行解（0-1向量）都可以构造出满足上述SDP约束的解（通过将 \( \mathbf{v}_ 0 \) 设为某个单位向量，\( \mathbf{v}_ i = \mathbf{v}_ 0 \) 若 \( x_ i=0 \)，或 \( \mathbf{v} i = -\mathbf{v} 0 \) 若 \( x_ i=1 \)，但注意这会导致 \( y {0i} = \pm 1 \)，而 \( x_ i = (1 - y {0i})/2 \) 给出了正确的01值，并且边约束被满足）。因此，SDP的最优值不大于原整数规划的最优值。 3. 算法步骤：求解与舍入 3.1 求解半定规划 我们可以使用内点法（如SeDuMi, SDPT3等求解器）来求解上述半定规划模型，得到最优的半正定矩阵 \( Y^* \) 和最优目标值 \( OPT_ {SDP} \)。由于 \( Y^* \) 是半正定的，我们可以通过 Cholesky分解 或特征值分解得到一个向量配置 \( \{\mathbf{v}_ 0^ , \mathbf{v}_ 1^ , ..., \mathbf{v} n^* \} \)，满足 \( y {ij}^* = \mathbf{v}_ i^* \cdot \mathbf{v}_ j^* \)。这些向量位于一个（至多）\( n+1 \) 维的单位球面上。 3.2 随机超平面舍入 (Randomized Hyperplane Rounding) 这是从连续向量解得到离散顶点覆盖的关键步骤。其思想来源于 Goemans-Williamson MAX-CUT算法 的舍入技术。 随机选取法向量 ：在 \( n+1 \) 维的单位球面上，均匀随机地选取一个单位向量 \( \mathbf{r} \)。 划分顶点 ：定义顶点覆盖 \( S \) 为满足 \( \mathbf{v}_ 0^* \cdot \mathbf{v}_ i^* \ge \mathbf{r} \cdot \mathbf{v}_ i^* \) 的顶点 \( i \) 的集合。一个等价的、更直观的几何操作是：考虑由法向量 \( \mathbf{r} \) 定义的随机超平面 \( H: \{ \mathbf{x} | \mathbf{r} \cdot \mathbf{x} = 0 \} \)。这个超平面将球面分成两个半球。我们将顶点 \( i \) 放入覆盖集 \( S \) 当且仅当向量 \( \mathbf{v}_ i^* \) 和 \( \mathbf{v}_ 0^* \) 落在该随机超平面的 同一侧 。即，如果 \( \text{sign}(\mathbf{r} \cdot \mathbf{v}_ i^ ) = \text{sign}(\mathbf{r} \cdot \mathbf{v}_ 0^ ) \)，则 \( i \in S \)。否则 \( i \notin S \)。 可行性修正 ：经过上述舍入得到的集合 \( S \) 不一定是一个合法的顶点覆盖。因为有可能某条边 \( (i, j) \) 的两个端点 \( \mathbf{v}_ i^* \) 和 \( \mathbf{v}_ j^* \) 都恰好与 \( \mathbf{v}_ 0^* \) 位于超平面异侧，从而均未被选中。但是，我们可以证明对于每条边 \( (i, j) \)，其两个端点都被舍入为“不在覆盖中”的概率是有限的。为了得到一个 必然可行 的解，我们采用以下策略：在舍入后，检查所有边。对于任何一条两个端点都不在 \( S \) 中的边，我们将其任意一个端点（例如编号较小的那个）加入 \( S \)。这一步保证了最终集合 \( S \) 是一个顶点覆盖。 4. 理论近似比分析 我们可以分析这个算法的期望近似比。 单顶点舍入概率 ：对于一个顶点 \( i \)，其被舍入到覆盖集 \( S \) 的概率（在修正前）等于其向量 \( \mathbf{v} i^* \) 与参考向量 \( \mathbf{v} 0^* \) 落在随机超平面同一侧的概率。在球面对称性下，这个概率等于 \( 1 - \frac{\theta {0i}}{\pi} \)，其中 \( \theta {0i} = \arccos(y_ {0i}^ ) \) 是向量 \( \mathbf{v}_ 0^ \) 和 \( \mathbf{v} i^* \) 之间的夹角。因此，\( P(i \in S {\text{initial}}) = 1 - \frac{\arccos(y_ {0i}^* )}{\pi} \)。 目标函数期望 ：初始覆盖集的期望大小为 \( E[ |S_ {\text{initial}}|] = \sum_ {i=1}^n \left(1 - \frac{\arccos(y_ {0i}^* )}{\pi} \right) \)。 与SDP目标的关系 ：SDP的目标是 \( OPT_ {SDP} = \frac{1}{2} \sum_ {i=1}^n (1 - y_ {0i}^* ) \)。 可以证明，对于 \( y \in [ -1, 1] \)，存在一个函数 \( \alpha \approx 1.114 \)（更精确地，\( \alpha = 2 / (1 - \cos(\pi/4)) \) 在特定的GW分析中出现，但对于顶点覆盖，经典的 Karant 分析给出近似比2），使得 \( 1 - \frac{\arccos(y)}{\pi} \le \alpha \cdot \frac{1}{2}(1 - y) \)。 因此，\( E[ |S_ {\text{initial}}|] \le \alpha \cdot OPT_ {SDP} \le \alpha \cdot OPT_ {IP} \)，其中 \( OPT_ {IP} \) 是原整数规划最优值。 可行性修正的成本 ：需要分析因为添加边端点而额外增加的顶点数期望。对于一条边 \( (i, j) \)，其两个端点初始都不在 \( S \) 中的概率是 \( \frac{\theta_ {ij}}{\pi} \)，其中 \( \theta_ {ij} = \arccos(y_ {ij}^ ) \)。由SDP约束 \( y_ {0i}^ + y_ {0j}^* \le 0 \) 和球面几何，可以推导出 \( \theta_ {ij} \ge \pi/2 \)，从而 \( \frac{\theta_ {ij}}{\pi} \ge 1/2 \)。然而，在修正时，我们只添加一个端点。通过更精细的概率分析（考虑每条边被修正的概率及其对期望大小的贡献），结合SDP约束，可以证明最终得到的覆盖集 \( S \) 的期望大小满足 \( E[ |S|] \le 2 \cdot OPT_ {SDP} \le 2 \cdot OPT_ {IP} \)。 这就是著名的 基于SDP松弛的随机舍入算法对于最小顶点覆盖问题的2-近似算法 。虽然期望近似比是2，但通过多次运行随机舍入并取最小的可行解，可以以高概率得到接近2倍最优解的解。 5. 一个简单算例 考虑一个三角形图（3个顶点，3条边）：\( V = \{1,2,3\} \), \( E = \{(1,2), (2,3), (1,3)\} \)。最小顶点覆盖大小为2（任意两个顶点即可）。 构建并求解SDP ： 变量：\( y_ {01}, y_ {02}, y_ {03}, y_ {12}, y_ {13}, y_ {23} \)。 目标：\( \min \frac{1}{2}[ (1-y_ {01}) + (1-y_ {02}) + (1-y_ {03}) ] \)。 约束： \( y_ {01} + y_ {02} \le 0 \) \( y_ {02} + y_ {03} \le 0 \) \( y_ {01} + y_ {03} \le 0 \) \( y_ {00}=y_ {11}=y_ {22}=y_ {33}=1 \) \( Y = \begin{bmatrix} 1 & y_ {01} & y_ {02} & y_ {03} \\ y_ {01} & 1 & y_ {12} & y_ {13} \\ y_ {02} & y_ {12} & 1 & y_ {23} \\ y_ {03} & y_ {13} & y_ {23} & 1 \end{bmatrix} \succeq 0 \) 一个最优解可以通过对称性猜测：\( y_ {01}^* = y_ {02}^* = y_ {03}^* = -\frac{1}{3} \)，并且 \( y_ {12}^* = y_ {13}^* = y_ {23}^* = \frac{1}{3} \)（可以验证矩阵 \( Y \) 是半正定的）。此时SDP目标值 = \( \frac{1}{2}[ (1+\frac{1}{3}) \times 3 ] = 2 \)。恰好等于整数最优解。 向量构造 ： 我们可以找到一个4维向量配置（\( n+1=4 \)）来实现这个 \( Y^* \)（例如，通过特征值分解）。向量间夹角满足 \( \cos\theta_ {0i} = -\frac{1}{3} \)。 随机舍入 ： 随机选取超平面法向量 \( \mathbf{r} \)。对于每个顶点 \( i \)，判断 \( \mathbf{v}_ i^* \) 是否与 \( \mathbf{v}_ 0^* \) 在 \( \mathbf{r} \) 定义的超平面同侧。 由于对称性，每个顶点被选入初始覆盖集的概率为 \( 1 - \frac{\arccos(-1/3)}{\pi} \approx 1 - (1.9106 / \pi) \approx 1 - 0.6082 = 0.3918 \)。 初始覆盖集大小的期望约为 \( 3 \times 0.3918 = 1.1754 < 2 \)。 但此时初始集很可能不是可行覆盖（例如，三条边可能都没有被覆盖）。进行可行性修正：检查所有边，将未被覆盖的边的某个端点加入。由于图很小，可以枚举情况。最终得到的覆盖集大小期望值会上升到2，与理论分析的2倍近似比一致。实际上，由于SDP目标值已经是2，任何可行覆盖的大小至少是2，而我们的算法期望产出大小为2的覆盖，这表明对于这个例子，算法是期望最优的。 6. 总结 本示例介绍了求解最小顶点覆盖问题的一种高级方法： 建立半定规划松弛模型 ，将0-1变量松弛为高维球面上的向量。 求解SDP 得到最优向量配置。 使用随机超平面舍入 ，将连续向量解转化为离散的顶点子集。 进行简单的可行性修正 ，确保结果是一个顶点覆盖。 该方法提供了期望下的2-近似保证，是经典线性规划舍入（也是2-近似）的一个有趣替代，有时在实践中能获得更好的经验性能。此方法展示了如何将组合优化问题嵌入连续向量空间，并利用几何概率工具进行分析和设计算法。