Goemans-Williamson の最大カットの近似アルゴリズムを紹介します。

最大カットの大きさを求める問題は次のように言い換えられます。
\begin{matrix}
\max &:& \frac{1}{2} \sum_{\{i,j\} \in E(G)} (1-w_iw_j) \\
\mbox{sub.to} &:& w_i \in \{ -1, 1 \} \\
\end{matrix}
\(w_i\) は各頂点に割り振られた重みで、\(w_v = 1\) となる頂点の集合 \(A\) と \(w_v=-1\) となる頂点の集合 \(B\) のカットの大きさが \(\frac{1}{2} \sum_{\{i,j\} \in E(G)} (1-w_iw_j)\) となります。これは、両端点 \(i,j\) が同じ集合に含まれる辺 \(e\) の重みは \(1-w_iw_j=0\)、異なる集合に含まれる辺の重みは \(1-w_iw_j=2\) となることから分かります。

この緩和問題として
\begin{matrix}
\max &:& \frac{1}{2} \sum_{\{i,j\} \in E(G)} (1-y_i \cdot y_j) \\
\mbox{sub.to} &:& y_i \cdot y_i = 1 \\
&:& y_i \in \mathbb{R}^n \\
\end{matrix}
を考えます。半正定値計画問題の形になっているので、絶対誤差 \(\varepsilon\) 以内で \(\log(1/\varepsilon)\) の多項式時間で解くことができます。更に、\(y_i=(w_i,0,0,\ldots,0)\) とすると元の問題の実行可能解になるので、この問題の最適値は元の問題以上になります。
\(r \in\mathbb{R}^n\) を平均 0 、分散 1 の正規分布から選び、\(r \cdot y_i \geq 0\) ならば \(w_i = 1\) さもなくば \(w_i = -1\) として元の問題の近似解を作ります。これは、単位球面上に位置する \(y_i\) たちについて、原点を通り \(r\) に垂直な超平面の上（\(r \cdot y_i \geq 0\)）と下（\(r \cdot y_i < 0\)）のどちらにあるかで分離してカットを作ることに対応します。

辺 \(\{i,j\}\) がカットに選ばれる確率は \(y_i\) と \(y_j\) のなす角 \(\theta_{ij}\) を固定して、\(r\) をランダムにすると、\(\theta/\pi\) です。緩和問題から得るカットの大きさの期待値 \(E(C)\) は \(\frac{1}{\pi}\arccos(x) \geq \alpha\frac{1}{2}(1-x)\) となる \(\alpha\) を用いて

\begin{align}
E\left[C\right] =&\sum_{\{i,j\}\in E}\theta_{ij}/\pi \\
=& \frac{1}{\pi}\sum_{\{ij\} \in E} \arccos(y_i \cdot y_j) \\
\geq & \alpha \sum_{\{i,j\}\in E}\frac{1}{2}(1 – y_i \cdot y_j)
\end{align}
として下から抑えられます。従って、
\(\alpha \cdot \mathrm{MAXCUT} \leq E(C) \leq \mathrm{MAXCUT}\)
となります。具体的には \(\alpha=0.868..\) となります。