基于线性规划的图最小边支配集问题的半定规划松弛求解示例
题目描述：
给定一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。一个边支配集是指边的子集 \(D \subseteq E\)，使得图中的每一条边至少与 \(D\) 中的一条边相邻（即共享一个公共顶点）。目标是找到最小的边支配集，即最小化 \(|D|\)。这是一个NP难问题，我们可以通过半定规划松弛来构造近似算法。本题目要求你基于半定规划松弛，设计一个求解最小边支配集问题的近似方案，并分析其近似比。
解题过程循序渐进讲解：
步骤1：问题建模为整数规划
首先，为每条边 \(e \in E\) 引入一个二进制变量 \(x_e \in \{0, 1\}\)，其中 \(x_e = 1\) 表示边 \(e\) 被选入边支配集 \(D\)。对于任意边 \(e = (u, v) \in E\)，它被支配的条件是：至少有一条与它相邻的边被选中。
与边 \(e\) 相邻的边集合包括：所有与顶点 \(u\) 关联的边（记为 \(\delta(u)\)）和与顶点 \(v\) 关联的边（记为 \(\delta(v)\)），但注意 \(e\) 本身也属于这两个集合。为了避免重复，支配条件可写为：
\[\sum_{f \in \delta(u)} x_f + \sum_{f \in \delta(v)} x_f - x_e \ge 1 \quad \text{对每条边 } e = (u, v) \in E. \]
目标是最小化所选边的总数：\(\min \sum_{e \in E} x_e\)。这是一个整数规划（IP）模型，但直接求解困难。
步骤2：构造半定规划松弛
半定规划（SDP）是线性规划的推广，允许变量为半正定矩阵。为利用SDP，我们将每条边 \(e\) 与一个单位向量 \(\mathbf{v}_e \in \mathbb{R}^n\) 关联。对于每条边 \(e\)，定义辅助变量 \(y_e = \frac{1 - \mathbf{v}_0 \cdot \mathbf{v}_e}{2}\)，其中 \(\mathbf{v}_0\) 是一个固定的单位参考向量。通过巧妙设计，可以用向量内积表达边之间的相邻关系。
考虑以下SDP松弛模型：
- 变量：对每条边 \(e\)，关联一个单位向量 \(\mathbf{v}_e\)（即 \(\|\mathbf{v}_e\| = 1\)），并引入固定参考向量 \(\mathbf{v}_0\)（也是单位向量）。
- 约束：对每条边 \(e = (u, v)\)，其相邻边的向量应满足“覆盖”条件。利用内积形式，可写为：
\[ \sum_{f \in \delta(u)} (1 - \mathbf{v}_0 \cdot \mathbf{v}_f) + \sum_{f \in \delta(v)} (1 - \mathbf{v}_0 \cdot \mathbf{v}_f) - (1 - \mathbf{v}_0 \cdot \mathbf{v}_e) \ge 2. \]
化简得：
\[ \sum_{f \in \delta(u) \cup \delta(v)} (1 - \mathbf{v}_0 \cdot \mathbf{v}_f) \ge 2 + (1 - \mathbf{v}_0 \cdot \mathbf{v}_e). \]
- 目标：最小化 \(\sum_{e \in E} \frac{1 - \mathbf{v}_0 \cdot \mathbf{v}_e}{2}\)，这对应于原问题中 \(x_e\) 的松弛形式。
步骤3：求解SDP松弛
上述SDP模型可以用内点法等多项式时间算法求解，得到一组最优向量 \(\{ \mathbf{v}_e^* \}\) 和最优目标值 \(OPT_{SDP}\)。由于是松弛，有 \(OPT_{SDP} \le OPT\)，其中 \(OPT\) 是原整数规划的最优值。
步骤4：舍入得到整数解
采用随机超平面舍入法：
- 随机选取一个单位向量 \(\mathbf{r}\)（均匀分布在单位球面上）。
- 对每条边 \(e\)，计算其向量 \(\mathbf{v}_e^*\) 与参考向量 \(\mathbf{v}_0\) 之间的角度关系。具体地，定义集合
\[ D = \{ e \in E \mid \mathbf{v}_0 \cdot \mathbf{v}_e^* \le \mathbf{r} \cdot \mathbf{v}_e^* \ \text{且} \ \mathbf{v}_0 \cdot \mathbf{v}_e^* \le \mathbf{r} \cdot \mathbf{v}_0 \}. \]
直观上，这表示当 \(\mathbf{v}_e^*\) 在几何上更靠近随机方向 \(\mathbf{r}\) 而非固定参考方向 \(\mathbf{v}_0\) 时，将边 \(e\) 选入支配集。
3. 输出 \(D\) 作为边支配集。
步骤5：近似比分析
可以证明，对每条边 \(e\)，其被支配的概率（即至少有一条相邻边在 \(D\) 中）至少为 \(1 - 1/e\)（约 0.632）。通过条件期望或贪婪修正，可确保得到可行解。进一步分析期望代价：
\[\mathbb{E}[|D|] = \sum_{e \in E} \Pr[e \in D] = \sum_{e \in E} \frac{1 - \mathbf{v}_0 \cdot \mathbf{v}_e^*}{2} = OPT_{SDP} \le OPT. \]
但这是期望大小，实际上舍入可能破坏某些边的支配条件。需进行后处理：若某条边未被支配，则加入其任意一条相邻边。这会增加代价，但可证明总代价不超过 \(2 \cdot OPT_{SDP}\)。结合SDP松弛的下界，得到近似比不超过 2。更精细的分析（利用SDP的几何结构）可将近似比改进到 1.5。
步骤6：算法总结
- 将最小边支配集问题建模为整数规划。
- 通过向量表示构造半定规划松弛，并求解。
- 使用随机超平面舍入得到候选边集。
- 检查并补充未支配的边，确保解可行。
- 输出最终边支配集，其大小至多为最优解的 1.5 倍（或 2 倍，取决于分析细节）。
此方法展示了如何利用半定规划松弛处理组合优化问题，并获得有理论保证的近似解。