UA MATH567 高維統計II 隨機向量9 圖的Max-cut問題 0.878近似算法

上一講我們用整數規劃對MAX-CUT問題建了模，$$\begin{gathered} CUT(G,x)=\frac{1}{2}\sum _{x_i{x}_j=?1}{A}_{ij}=\frac{1}{4}\sum _{i,j}{A}_{ij}(1?x_i{x}_j) \\ =\frac{1}{4}\sum _{i,j}{A}_{ij}?\frac{1}{4}\sum _{i,j}{A}_{ij}{x}_i{x}_j \end{gathered}$$第一項是常數，于是
$$MAX?CUT(G)=\underset{x}{\max }CUT(G,x)?\underset{x\in \{?1,1{\}}^n}{\min }{x}^{T}Ax$$并且我們給了一個0.5 approximation algorithm，這一講我們討論一個更先進的0.878-approximation algorithm。

---

上上上講我們介紹了用半正定規劃近似整數規劃，既然MAX-CUT問題可以用整數規劃建模，那么我們也可以用半正定規劃來近似$MAX?CUT(G)$，也就是
$$SDP(G)=\frac{1}{4}\underset{{\Vert X_i\Vert }_2=1}{\max }\{\sum _{i,j}{A}_{ij}(1??X_i,X_j?)\}$$

根據relaxation的性質，
$$SDP(G)\ge MAX?CUT(G)$$

下面我們推導用半正定規劃近似max-cut的效果：

假設$X_1,?,X_n$是$SDP(G)$的解，我們做random rounding，即定義$g～N(0,I_n)$，定義$x_i=sgn(?X_i,g?)$，使用$x=(x_1,?,x_n)$，我們可以計算$ECUT(G,x)$，可以證明
$$ECUT(G,x)\ge 0.878SDP(G)\ge 0.878MAX?CUT(G)$$

稱這個近似為0.878-approximation algorithm。

---

引理 Grothendieck恒等式
$u,v\in S^{n?1}$，$g\in N(0,I_n)$，則
$$E(sgn?g,u?sgn?g,v?)=\frac{2}{\pi }\arcsin ?u,v?$$

證明
假設$u,v$的夾角($n$維單位球的球心角)為$\theta$，則
$$sgn?g,u?sgn?g,v?=\{\begin{array}{l}1,withprob1?\pi /\theta \\ ?1,withprob\pi /\theta \end{array}$$

因此
$$E[sgn?g,u?sgn?g,v?]=\frac{\pi ?2\theta }{\pi }$$

其中$\theta =\arccos ?u,v?$，
$$\begin{gathered} E[sgn?g,u?sgn?g,v?]=\frac{2}{\pi }(\frac{\pi }{2}?\arccos ?u,v?) \\ =\frac{2}{\pi }\arcsin ?u,v? \end{gathered}$$

---

證明0.878近似
$$\begin{gathered} ECUT(G,x)=E\frac{1}{4}\sum _{i,j}{A}_{ij}(1?x_i{x}_j)=\frac{1}{4}\sum _{i,j}{A}_{ij}(1?E{x}_i{x}_j) \\ =\frac{1}{4}\sum _{i,j}{A}_{ij}(1?Esgn(?X_i,g?)sgn(?X_j,g?)) \\ =\frac{1}{4}\sum _{i,j}{A}_{ij}(1?\frac{2}{\pi }\arcsin ?X_i,X_j?) \end{gathered}$$

最后一步用的Grothendieck恒等式。我們繼續計算
$$\frac{1}{4}\sum _{i,j}{A}_{ij}(1?\frac{2}{\pi }\arcsin ?X_i,X_j?)=\frac{1}{4}\sum _{i,j}{A}_{ij}\frac{2}{\pi }\arccos ?X_i,X_j?$$

希望看到的結果是
$$\frac{2}{\pi }\arccos ?X_i,X_j?\ge C(1??X_i,X_j?)$$

這樣我們就可以得到
$$ECUT(G,x)\ge C\times SDP(G)$$

畫出$\frac{2\arccos (x)}{\pi (1?x)}$的圖像，就可以發現0.878是最小值了（0.879是近似的結果）

總結

以上是生活随笔為你收集整理的UA MATH567 高维统计II 随机向量9 图的Max-cut问题 0.878近似算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。