Goemans–Williamson Max-Cut 近似

形式陈述

问题与 SDP 上界

给定有限简单无向图 $G=(V,E)$ ，每条边另带有限非负权 $w_{ij}$ 。空图或总边权为零时返回任意割，目标值精确为零；以下设 $n=|V|\ge2$ 且总边权为正。用 $x_i\in\{-1,+1\}$ 表示顶点位于割的哪一侧，Max-Cut 的整数目标为

\operatorname{OPT} =\max_{x\in\{-1,+1\}^V} \frac12\sum_{\{i,j\}\in E} w_{ij}(1-x_ix_j).

把标量符号换成任意维单位向量 $v_i$ ，得到半正定松弛

\operatorname{SDP} =\max_{\|v_i\|_2=1} \frac12\sum_{\{i,j\}\in E} w_{ij}(1-\langle v_i,v_j\rangle).

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

\operatorname{SDP}\ge\operatorname{OPT}.

有限有理权重的编码模型下，可将该 SDP 求解到指定加性精度；时间还依赖输入位长和精度参数。以下核心比率先假设所选单位向量精确可行且达到 SDP 最优值，并采用理想连续抽样模型；随后说明只取得近似最优目标值时的误差怎样进入结果。

随机超平面舍入

在所选向量的维数 $d\ge1$ 中抽取联合标准高斯向量 $g\sim N_d(0,I_d)$ ，等价地独立抽取 $d$ 个标准正态坐标。对任意正交矩阵 $Q$ ，仿射变换公式给出 $Qg\sim N_d(0,QI_dQ^\top)=N_d(0,I_d)$ ，所以分布具有正交不变性，方向 $g/\|g\|$ 在单位球面上均匀。输出

x_i=\operatorname{sign}\langle g,v_i\rangle,

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

给定已存储的 $n$ 个 $\mathbb R^d$ 单位向量，一轮舍入需要 $d$ 次标量高斯抽样；在单位成本算术模型下，计算全部符号并评估割权需要 $O(nd+|E|)$ 次算术操作，向量存储为 $O(nd)$ 个标量。SDP 求解与 Gram 分解的成本另计；这些计数并不包含有限精度抽样、数值误差控制或各标量的位存储成本。

若 $v_i,v_j$ 的夹角为

\theta_{ij}=\arccos\langle v_i,v_j\rangle\in[0,\pi],

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

\Pr[x_i\ne x_j]=\frac{\theta_{ij}}{\pi}.

当 $0<\theta_{ij}<\pi$ 时，证明可限制在二者张成的二维平面：高斯投影的方向在 $[0,2\pi)$ 均匀，使两个内积符号相反的两段角域各长 $\theta_{ij}$ ，故概率为 $2\theta_{ij}/(2\pi)$ 。共线端点 $\theta=0,\pi$ 分别直接给出概率 $0,1$ 。

0.87856 常数来自一次最小化

SDP 中该边的单位权贡献为

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

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

\alpha_{\mathrm{GW}} =\min_{\theta\in(0,\pi]} \frac{\theta/\pi}{(1-\cos\theta)/2} =\min_{\theta\in(0,\pi]} \frac{2\theta}{\pi(1-\cos\theta)} \approx0.878567.

$\theta=0$ 时分母为零，所以不把它放进比值的定义域；此处逐边不等式两侧都是零。正角度的比值在 $\theta\downarrow0$ 时趋于无穷，最小值在内部取得。内点极小值满足

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

（数值上 $\theta\approx2.3311$ ）。令 $h(\theta)=1-\cos\theta-\theta\sin\theta$ ，其导数为 $-\theta\cos\theta$ ，故先在 $(0,\pi/2)$ 下降，再在 $(\pi/2,\pi)$ 上升；后一区间只有一个零点，正是比值的唯一极小点。因此对每条边分别有

\frac{\theta_{ij}}{\pi} \ge\alpha_{\mathrm{GW}} \frac{1-\cos\theta_{ij}}2.

由期望线性性，不需要各边切割事件独立：

\begin{aligned} \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-\langle v_i,v_j\rangle}{2}\\ &=\alpha_{\mathrm{GW}}\operatorname{SDP}\\ &\ge\alpha_{\mathrm{GW}}\operatorname{OPT}. \end{aligned}

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

直觉

SDP 把二元割侧放松成球面上的单位向量，向量夹角同时控制松弛目标与随机超平面分开两个端点的概率。对每个可能夹角比较这两种贡献并取最坏比值，得到统一常数；边事件即使相关，期望线性性仍允许逐边相加。

单位向量夹角经随机超平面转化为 Max-Cut 切边概率 — 向量角度与随机切割

例子与边界

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

无权三角形 $K_3$ 的最大割权为 $2$ 。SDP 可把三个单位向量放成两两夹角 $120^\circ=2\pi/3$ ，每条边的 SDP 贡献为 $3/4$ ，总 SDP 值 $9/4$ 。对任意三个单位向量， $0\le\|v_1+v_2+v_3\|^2=3+2\sum_{i<j}\langle v_i,v_j\rangle$ ，所以松弛目标至多 $9/4$ ；该构型确实达到 SDP 最优。随机超平面分开任意一对的概率为 $2/3$ ，所以期望切边数为

3\cdot\frac23=2,

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

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

从期望到可重复保证

单次随机舍入给的是期望近似，不是“每次至少 $0.87856\operatorname{OPT}$ ”。在当前总权为正、精确 SDP 解的分支， $\operatorname{SDP}>0$ ，且输出割权 $W$ 位于 $[0,\operatorname{OPT}]\subseteq[0,\operatorname{SDP}]$ 。取 $0<\eta<\alpha_{\rm GW}$ ，由有界性可将

\Pr\!\left[ w(\delta(S))\ge (\alpha_{\mathrm{GW}}-\eta)\operatorname{SDP} \right]

下界为 $p_0=\eta/(1-\alpha_{\rm GW}+\eta)>0$ ：若该事件概率为 $p$ ，则 $\mathbb EW/\operatorname{SDP}\le(\alpha_{\rm GW}-\eta)(1-p)+p$ ，与期望下界比较即可。独立重复 $t$ 次并保留最好割，失败概率至多 $(1-p_0)^t\le e^{-p_0t}$ ；取 $t\ge p_0^{-1}\ln(1/\delta)$ 即可使其不超过 $0<\delta<1$ 。也可用条件期望逐步固定超平面随机性获得去随机化版本，但这需要能计算相应条件概率。

失败边界与近邻舍入

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

若先得到精确可行单位向量，其松弛目标值为 $L\ge\operatorname{SDP}-\tau$ ，则同一逐边证明给出 $\mathbb EW\ge\alpha_{\rm GW}L\ge\alpha_{\rm GW}\operatorname{OPT}-\alpha_{\rm GW}\tau$ 。设总边权为 $W_{\rm tot}>0$ ，独立公平分边的期望为 $W_{\rm tot}/2$ ，故 $\operatorname{OPT}\ge W_{\rm tot}/2$ ；例如选 $\tau\le\varepsilon W_{\rm tot}/(2\alpha_{\rm GW})$ 就得到 $(\alpha_{\rm GW}-\varepsilon)\operatorname{OPT}$ 的期望界。数值 Gram 矩阵还须先修复可行性并将修复的目标变化计入 $\tau$ ；有限位抽样另有分布与符号误差，不能凭连续高斯公式把这些成本省掉。 $\operatorname{SDP}\ge\operatorname{OPT}$ 是最大化松弛的方向；误写成下界会让近似链最后一步反向。

推论与应用

随机超平面舍入成为半正定近似算法的标准接口：先由向量解捕捉全局相关性，再把几何关系转成离散选择。它可扩展到若干约束满足与图划分松弛，但每个变体都要重新核对目标权重符号、几何约束和逐项概率不等式。

随机超平面角度指纹复用本页的分离概率，却输出另一种对象：同一共享配置下的规范位串及Hamming比例估计。多张独立平面给固定向量对带来方差和尾界，字节布局、配置身份与零点积规则则决定这些指纹能否合法比较；看过配置再从共同零空间挑向量，不能继续沿用固定对象的保证。

参考资料

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，§§2–3：有限精度接口、角度概率及常数最小化。
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.

形式陈述 ​

问题与 SDP 上界 ​

随机超平面舍入 ​

0.87856 常数来自一次最小化 ​

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

从期望到可重复保证 ​

失败边界与近邻舍入 ​

反向链接