UA MATH567 高維統計II 隨機向量8 圖的Max-cut問題 0.5近似算法的運行時間分析

我們之前討論了圖的max-cut問題的0.5近似算法，也就是給定一張圖，按擲硬幣的概率決定是否切開一條邊，這樣的算法平均能切開一半的邊：

$$\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}$$

假設$x～Unif(\{?1,1{\}}^n)$，則
$$ECUT(G,x)=\frac{1}{2}|E|\ge \frac{1}{2}MAX?CUT(G)$$

說明
$$\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?E{x}_{i}E{x}_j)=\frac{1}{4}\sum _{i,j}{A}_{ij}=\frac{1}{2}|E| \end{gathered}$$

也就是說我們按均勻分布的思路隨機對每個頂點分類，這樣得到的分割平均可以“切開”一半的邊，稱這個結果為0.5-approximation algorithm。

現在我們討論一下這個算法需要的時間，也就是經過多少次"切割"我們才能得到0.5近似。

---

為了便于討論，$??>0$，我們分析$(0.5??)$-近似算法：
$$CUT(G,x)\ge (0.5??)MAX?CUT(G)$$

嘗試找到它的平均運行時間。記
$$P_{?}=P(CUT(G,x)\ge (0.5??)MAX?CUT(G))$$

則平均運行時間與$1/P_{?}$成正比，根據定義
$$\begin{gathered} ECUT(G,x)\ge \frac{1}{2}MAX?CUT(G) \\ ECUT(G,x)\le P_{?}MAX?CUT(G) \\ +(1?P_{?})(0.5??)MAX?CUT(G)) \end{gathered}$$

于是
$$\begin{gathered} \frac{1}{2}MAX?CUT(G)\le P_{?}MAX?CUT(G) \\ +(1?P_{?})(0.5??)MAX?CUT(G)) \end{gathered}$$

消去$MAX?CUT(G)$，我們可以得到
$$P_{?}\ge \frac{?}{0.5+?}$$

于是預計的抽樣次數為
$$1/P_{?}\le 1+\frac{1}{2?}$$

總結

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

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