Goemans–Williamson Max-Cut 近似

问题与 SDP 上界 ​

给定无向图 $G=(V,E,w)$，边权 $w_{ij}\ge 0$。用 $x_i\in \{-1,+1\}$ 表示顶点位于割的哪一侧，Max-Cut 的整数目标为

$$\mathrm{OPT}=\underset{x\in \{-1,+1{\}}^V}{max}\frac{1}{2}\sum _{\{i,j\}\in E}{w}_{ij}(1-x_i{x}_j).$$

把标量符号换成任意维单位向量 $v_i$，得到 半正定松弛公理库半正定规划松弛semidefinite relaxation · SDP relaxation把 ±1 二次变量提升为单位向量或 Gram 矩阵，获得可凸优化的上界并连接随机舍入。

$$\mathrm{SDP}=\underset{\Vert v_i{\Vert }_2=1}{max}\frac{1}{2}\sum _{\{i,j\}\in E}{w}_{ij}(1-⟨v_i,v_j⟩).$$

等价 Gram 矩阵形式是 $X⪰0$、$X_{ii}=1$。每个整数解对应所有 $v_i$ 落在同一条直线的可行向量解，所以这是最大化问题的上界：

$$\mathrm{SDP}\ge \mathrm{OPT}.$$

多项式时间内把 SDP 解到足够小的加性精度后，舍入损失中还要保留该精度；以下先按精确 SDP 解陈述核心比率。

随机超平面舍入 ​

从标准高斯分布取向量 $g$；方向 $g/\Vert g\Vert$ 在单位球面上均匀。输出

$$x_i=\mathrm{sign}⟨g,v_i⟩,$$

零内积事件概率为零，可任意约定。所有顶点共享同一个随机超平面，因此舍入高度相关；它不是对每个坐标独立抛硬币。

若 $v_i,v_j$ 的夹角为

$${\theta }_{ij}=\arccos ⟨v_i,v_j⟩\in [0,\pi ],$$

则随机超平面分开二者的概率为

$$\text{Pr}[x_i\ne x_j]=\frac{{\theta }_{ij}}{\pi }.$$

证明可限制在 $v_i,v_j$ 张成的二维平面：超平面法向方向落入使两个投影符号相反的两段角域，总角度占整个无向法向角域的 ${\theta }_{ij}/\pi$。

0.87856 常数来自一次最小化 ​

SDP 中该边的单位权贡献为

$$\frac{1-\cos \theta }{2},$$

舍入后期望贡献为 $\theta /\pi$。定义

$${\alpha }_{\mathrm{GW}}=\underset{\theta \in [0,\pi ]}{min}\frac{\theta /\pi }{(1-\cos \theta )/2}=\underset{\theta \in [0,\pi ]}{min}\frac{2\theta }{\pi (1-\cos \theta )}\approx 0.878567.$$

内点极小值满足

$$1-\cos \theta =\theta \sin \theta$$

（数值上 $\theta \approx 2.3311$）。因此对每条边分别有

$$\frac{{\theta }_{ij}}{\pi }\ge {\alpha }_{\mathrm{GW}}\frac{1-\cos {\theta }_{ij}}{2}.$$

由 期望线性性公理库期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分。，不需要各边切割事件独立：

$$\begin{array}{rl}\mathbb{E}[w(\delta (S))]& =\sum _{\{i,j\}}{w}_{ij}\frac{{\theta }_{ij}}{\pi }\\ & \ge {\alpha }_{\mathrm{GW}}\sum _{\{i,j\}}{w}_{ij}\frac{1-⟨v_i,v_j⟩}{2}\\ & ={\alpha }_{\mathrm{GW}}\mathrm{SDP}\\ & \ge {\alpha }_{\mathrm{GW}}\mathrm{OPT}.\end{array}$$

这才是 $0.87856$ 比率的来源；只写“角度除以 $\pi$”不会自动给出统一近似常数。

具体例子：三角形达到最优期望 ​

无权三角形 $K_3$ 的最大割权为 $2$。SDP 可把三个单位向量放成两两夹角 ${120}^{\circ }=2\pi /3$，每条边的 SDP 贡献为 $3/4$，总 SDP 值 $9/4$。随机超平面分开任意一对的概率为 $2/3$，所以期望切边数为

$$3\cdot \frac{2}{3}=2,$$

恰等于整数最优值。三个边事件显然相关——三角形的割不可能只切一条或三条边——但期望分析仍逐边相加。

在端点向量相同的边上 $\theta =0$，该边从不被切且 SDP 贡献为零；相反向量的边上 $\theta =\pi$，它必被切且 SDP 贡献为一。这两个边界与概率公式一致。

从期望到可重复保证 ​

单次随机舍入给的是期望近似，不是“每次至少 $0.87856\mathrm{OPT}$”。由于输出割权位于 $[0,\mathrm{SDP}]$，对任意 $\eta >0$ 可由有界性把

$$\text{Pr}[w(\delta (S))\ge ({\alpha }_{\mathrm{GW}}-\eta )\mathrm{SDP}]$$

下界为只依赖 $\eta$ 的正常数；独立重复舍入并保留最好割，可把未达到稍弱比率的概率指数降低。也可用条件期望逐步固定超平面随机性获得去随机化版本，但这需要能计算相应条件概率。

失败边界与近邻舍入 ​

算法与比率针对无向、非负权 Max-Cut。负权边使“切得越多越好”的逐边下界失效；有向 Max-Cut 和带额外平衡约束的版本有不同松弛与比率。逐顶点独立舍入会丢掉 SDP 向量间的角度相关性，不能复用同一证明。

数值 SDP 求解只得到近似可行 Gram 矩阵，需把可行性修复和目标加性误差计入最终保证。$\mathrm{SDP}\ge \mathrm{OPT}$ 是最大化松弛的方向；误写成下界会让近似链最后一步反向。

参考资料

• Michel X. Goemans and David P. Williamson, “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming,” Journal of the ACM 42(6), 1995, 1115–1145.
• David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, semidefinite programming chapter.
• Vijay V. Vazirani, Approximation Algorithms, Springer, 2001, Max-Cut and SDP rounding.