UA MATH567 高维统计II 随机向量9 图的Max-cut问题 0.878近似算法
UA MATH567 高维统计II 随机向量9 图的Max-cut问题 0.878近似算法
上一讲我们用整数规划对MAX-CUT问题建了模，CUT(G,x)=12∑xixj=−1Aij=14∑i,jAij(1−xixj)=14∑i,jAij−14∑i,jAijxixjCUT(G,x)=\frac{1}{2}\sum_{x_ix_j=-1}A_{ij} = \frac{1}{4}\sum_{i,j}A_{ij}(1-x_ix_j) \\ = \frac{1}{4}\sum_{i,j}A_{ij}-\frac{1}{4}\sum_{i,j}A_{ij} x_ix_jCUT(G,x)=21xixj=−1∑Aij=41i,j∑Aij(1−xixj)=41i,j∑Aij−41i,j∑Aijxixj第一项是常数，于是
MAX−CUT(G)=maxxCUT(G,x)⇔minx∈{−1,1}nxTAxMAX-CUT(G)=\max_x CUT(G,x) \Leftrightarrow \min_{x \in \{-1,1\}^n} x^TAxMAX−CUT(G)=xmaxCUT(G,x)⇔x∈{−1,1}nminxTAx并且我们给了一个0.5 approximation algorithm，这一讲我们讨论一个更先进的0.878-approximation algorithm。
上上上讲我们介绍了用半正定规划近似整数规划，既然MAX-CUT问题可以用整数规划建模，那么我们也可以用半正定规划来近似MAX−CUT(G)MAX-CUT(G)MAX−CUT(G)，也就是
SDP(G)=14max∥Xi∥2=1{∑i,jAij(1−⟨Xi,Xj⟩)}SDP(G)=\frac{1}{4}\max_{\left\| X_i \right\|_2=1}\{\sum_{i,j}A_{ij}(1-\langle X_i,X_j \rangle)\}SDP(G)=41∥Xi∥2=1max{i,j∑Aij(1−⟨Xi,Xj⟩)}
根据relaxation的性质，
SDP(G)≥MAX−CUT(G)SDP(G) \ge MAX-CUT(G)SDP(G)≥MAX−CUT(G)
下面我们推导用半正定规划近似max-cut的效果：
假设X1,⋯,XnX_1,\cdots,X_nX1,⋯,Xn是SDP(G)SDP(G)SDP(G)的解，我们做random rounding，即定义g∼N(0,In)g \sim N(0,I_n)g∼N(0,In)，定义xi=sgn(⟨Xi,g⟩)x_i = sgn(\langle X_i,g \rangle)xi=sgn(⟨Xi,g⟩)，使用x=(x1,⋯,xn)x = (x_1,\cdots,x_n)x=(x1,⋯,xn)，我们可以计算ECUT(G,x)ECUT(G,x)ECUT(G,x)，可以证明
ECUT(G,x)≥0.878SDP(G)≥0.878MAX−CUT(G)ECUT(G,x) \ge 0.878 SDP(G) \ge 0.878MAX-CUT(G)ECUT(G,x)≥0.878SDP(G)≥0.878MAX−CUT(G)
称这个近似为0.878-approximation algorithm。
引理 Grothendieck恒等式
u,v∈Sn−1u,v \in S^{n-1}u,v∈Sn−1，g∈N(0,In)g \in N(0,I_n)g∈N(0,In)，则
E(sgn⟨g,u⟩sgn⟨g,v⟩)=2πarcsin⟨u,v⟩E(sgn \langle g,u \rangle sgn\langle g,v \rangle)=\frac{2}{\pi}\arcsin \langle u,v \rangleE(sgn⟨g,u⟩sgn⟨g,v⟩)=π2arcsin⟨u,v⟩
证明
假设u,vu,vu,v的夹角(nnn维单位球的球心角)为θ\thetaθ，则
sgn⟨g,u⟩sgn⟨g,v⟩={1,withprob1−π/θ−1,withprobπ/θsgn \langle g,u \rangle sgn\langle g,v \rangle = \begin{cases} 1, with \ prob \ 1-\pi/\theta \\ -1,with \ prob \ \pi/\theta \end{cases}sgn⟨g,u⟩sgn⟨g,v⟩={1,with prob 1−π/θ−1,with prob π/θ
因此
E[sgn⟨g,u⟩sgn⟨g,v⟩]=π−2θπE[sgn \langle g,u \rangle sgn\langle g,v \rangle]=\frac{\pi -2\theta}{\pi}E[sgn⟨g,u⟩sgn⟨g,v⟩]=ππ−2θ
其中θ=arccos⟨u,v⟩\theta = \arccos\langle u,v \rangleθ=arccos⟨u,v⟩，
E[sgn⟨g,u⟩sgn⟨g,v⟩]=2π(π2−arccos⟨u,v⟩)=2πarcsin⟨u,v⟩E[sgn \langle g,u \rangle sgn\langle g,v \rangle] = \frac{2}{\pi}(\frac{\pi}{2}-\arccos\langle u,v \rangle) \\ = \frac{2}{\pi}\arcsin \langle u,v \rangleE[sgn⟨g,u⟩sgn⟨g,v⟩]=π2(2π−arccos⟨u,v⟩)=π2arcsin⟨u,v⟩
证明0.878近似
ECUT(G,x)=E14∑i,jAij(1−xixj)=14∑i,jAij(1−Exixj)=14∑i,jAij(1−Esgn(⟨Xi,g⟩)sgn(⟨Xj,g⟩))=14∑i,jAij(1−2πarcsin⟨Xi,Xj⟩)ECUT(G,x) =E\frac{1}{4}\sum_{i,j}A_{ij}(1-x_ix_j) = \frac{1}{4}\sum_{i,j}A_{ij}(1-Ex_ix_j) \\ =\frac{1}{4}\sum_{i,j}A_{ij}(1-Esgn(\langle X_i,g \rangle)sgn(\langle X_j,g \rangle)) \\ = \frac{1}{4}\sum_{i,j}A_{ij}(1-\frac{2}{\pi}\arcsin \langle X_i,X_j \rangle) ECUT(G,x)=E41i,j∑Aij(1−xixj)=41i,j∑Aij(1−Exixj)=41i,j∑Aij(1−Esgn(⟨Xi,g⟩)sgn(⟨Xj,g⟩))=41i,j∑Aij(1−π2arcsin⟨Xi,Xj⟩)
最后一步用的Grothendieck恒等式。我们继续计算
14∑i,jAij(1−2πarcsin⟨Xi,Xj⟩)=14∑i,jAij2πarccos⟨Xi,Xj⟩\frac{1}{4}\sum_{i,j}A_{ij}(1-\frac{2}{\pi}\arcsin \langle X_i,X_j \rangle) = \frac{1}{4}\sum_{i,j}A_{ij}\frac{2}{\pi}\arccos \langle X_i,X_j \rangle41i,j∑Aij(1−π2arcsin⟨Xi,Xj⟩)=41i,j∑Aijπ2arccos⟨Xi,Xj⟩
希望看到的结果是
2πarccos⟨Xi,Xj⟩≥C(1−⟨Xi,Xj⟩)\frac{2}{\pi}\arccos \langle X_i,X_j \rangle \ge C(1- \langle X_i,X_j \rangle)π2arccos⟨Xi,Xj⟩≥C(1−⟨Xi,Xj⟩)
这样我们就可以得到
ECUT(G,x)≥C×SDP(G)ECUT(G,x) \ge C \times SDP(G)ECUT(G,x)≥C×SDP(G)
画出2arccos(x)π(1−x)\frac{2\arccos (x)}{\pi(1-x)}π(1−x)2arccos(x)的图像，就可以发现0.878是最小值了（0.879是近似的结果）
总结
以上是生活随笔为你收集整理的UA MATH567 高维统计II 随机向量9 图的Max-cut问题 0.878近似算法的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： UA MATH567 高维统计II 随机
- 下一篇： UA MATH567 高维统计II 随机