This is a short summary of approximation algorithms for the MaxCut problem of finding a maximum cut of a graph. After introducing the problem and trivial $\frac{1}{2}$approximation, we summarize the famous semidefinite programming relaxation and hyperplane rounding technique from (Goemans & Williamson, 1995) that gives the best known approximation ratio for MaxCut. We then take a look at the dual problem and some previous results. Taking the dual approach further, using socalled SumofSquares hierarchy framework with Gaussian rounding technique, we arrive at the same approximation ratio for MaxCut. Finally, we discuss some possible generalizations.
Table of contents
 Introduction
 Preliminaries
 SDP relaxation
 Hyperplane rounding
 Dual problem
 SoS relaxation
 Gaussian rounding
 Generalizations
 Source code
 References
Introduction
Let $G = (V, E)$ be a simple undirected graph with $V := \lbrace 1, \dots, n \rbrace$ and $E = m$. For a subset $S \subset V$, we define a $cut(S)$ as a subset of edges $E$ having one vertex in $S$ and the other one in $V \setminus S$. We denote the cut size by $f(S) = cut(S)$. The MaxCut problem is to find a subset $S \subseteq V$ that maximizes the cut size $f(S)$. MaxCut problem is NPcomplete (Karp, 1972).
Figure 1 shows a cycle graph $C_{5}$ where a subset $S = \lbrace{v_1, v_3\rbrace}$ gives a cut of maximum size 4.
Given a graph $G=(V,E)$, denote the maximum cut size by $mc(G)$. For a given algorithm that returns the subset $S \subseteq V$, we say that it is an $\alpha$approximation algorithm for MaxCut if
\[\begin{equation} f(S) \geq \alpha \cdot mc(G) \label{eq: alpha} \end{equation}\]for all graphs $G = (V, E)$ and some approximation ratio $\alpha \in [0, 1]$. If algorithm employed is randomized, meaning $S$ that it returns is a random variable, then we say the same, if (\ref{eq: alpha}) holds with an expectation taken on the lefthand side.
Example
An algorithm, that assigns each vertex to $S$ or $V \setminus S$ independently uniformly at random, is a $1/2$approximation for MaxCut:
\[\DeclareMathOperator{\Ex}{\mathbb{E}} \DeclareMathOperator{\Prob}{\mathbb{P}} \mathbb{E}[f(S)] = \sum_{i, j} \Prob[(i, j) \in \text{cut}(S)] = \frac{1}{2} \, m \geq \frac{1}{2} \cdot mc(G).\]This approximation was first proposed and analyzed by (Erdős, 1967).
In (Goemans & Williamson, 1995) they improved this by proposing $\alpha_{GW}$approximation algorithm with $\alpha_{GW} \geq 0.878$ using semidefinite programming (SDP) and hyperplane rounding technique. The proposed algorithm is easy to implement using offtheshelf SDP solver, see the Source code for more details.
Preliminaries
A real symmetric matrix $X$ is positive definite, denoted $X \succeq 0$ if the following equivalent conditions hold:
 All eigenvalues of $X$ are nonnegative.
 Quadratic form $v^{T}Xv \geq 0$ for all $v \in \mathbb{R}^{n}$.
 There exists $Q \in \mathbb{R}^{n \times r}$ with
where $v_{1}, \dots, v_{r}$ are columns of $Q$.
In the set of all symmetric matrices $S^{n}$, denote the convex cone of positive semidefinite matrices by
\[S^{n}_{+}.\]A spectrahedron is the intersection of $S^{n}_{+}$ with an affine linear space $A \bullet X = b$. Semidefinite programming (SDP) solves the problem (P) of maximizing (or minimizing) a linear objective function $C \bullet X$ over the spectrahedron:
\[\begin{align*} & \text{maximize} \ C \bullet X \\ & \text{subject to: } \tag{P}\\ & \qquad A_{i} \bullet X = b_{i} \quad i = 1, \dots, m \\ & \qquad X \succeq 0 \end{align*}\]The corresponding dual problem (D) is:
\[\begin{align*} & \text{minimize} \ b^{T}y \\ & \text{subject to: } \label{eq: P} \tag{D}\\ & \qquad \sum_{i=1}^{m} A_{i} y_{i}  C \succeq 0 \end{align*}\]Properties:

Every convex polyhedron is a spectrahedron.

Spectrahedron is a closed convex set.

Weak duality always holds:
 Under primal and dual feasibility, also strong duality holds:
More on semidefinite programming can be found in Chapter 12 (Michalek & Sturmfels, 2021).
SDP relaxation
Cuts in the complete graph $K_n$ can be represented by a set of $2^{n  1}$ matrices $x x^{T}$ of rank one with $x \in \lbrace 1, 1 \rbrace^{n}$. The $n \times n$ spectrahedron:
\[\mathcal{E}_{n} := \lbrace X \in S^{n}_{+} : X_{ii} = 1, \, \, \forall i \rbrace\]is called an elliptope. It is a set of all $n \times n$ correlation matrices.
It gives the following formulation of maximum cut problem:
\[mc(G) = \max_{X \in \mathcal{E}_{n}, rk(X) = 1 } \sum_{i, j} \frac{1  X_{ij}}{2} .\]Letting go of rank one constraint $rk(X) = 1$, we get an SDP problem:
\[sdp(G) := \max_{X \in \mathcal{E}_{n}} \sum_{i, j} \frac{1  X_{ij}}{2}.\]Since $\mathcal{E}_{n}$ includes all the matrices of rank one,
\[mc(G) \leq sdp(G).\]Therefore $sdp(G)$ is a relaxation.
Example
Cuts in complete graph $K_{3}$ can be represented by a set of matrices of rank one:
\[\lbrace x x^{T} : x \in \lbrace 1, 1 \rbrace^{3} \rbrace.\]These matrices are contained in $3 \times 3$ elliptope
\[\mathcal{E}_{3} = \lbrace (x_1, x_2, x_3)^{T} \in \mathbb{R}^{3} : \begin{pmatrix} 1 & x_1 & x_2 \\ x_1 & 1 & x_3 \\ x_2 & x_3 & 1 \end{pmatrix} \succeq 0 \rbrace.\]The boundary of $\mathcal{E}_{3}$ consists of all $(x_1, x_2, x_3)^{T} \in \mathbb{R}^{3}$ where determinant is 0:
\[(x_2 x_3  x_1) x_1 + (x_1 x_3  x_2) x_2  x_{3}^2 + 1 = 0.\]This is a cubic surface drawn in Figure 2 using Python and SageMath:
from sage.all import *
var('x,y,z')
f(x, y, z) = (y*z  x)*x + (x*z  y)*y  z^2 + 1
p = implicit_plot3d(f(x,y,z) == 0, (x,1,1), (y,1,1), (z,1,1),
opacity=0.9, plot_points=50, smooth=True)
p
Hyperplane rounding
Solution $X$ that realizes the maximum $sdp(G)$ is a positive semidefinite matrix that can be decomposed as $X=\sum_{i=1} v_{i}v_{i}^T$ for some unit vectors $v_{i}$. To construct a subset $S \subset V$, select a random unit vector $r \in \mathbb{R}^{n}$ and let $S = \lbrace i \in V : v_{i}^{T}r \geq 0 \rbrace$. Denote the angle between vectors $v_i, v_j$ by $\theta_{i, j}$.
Since $v_{i}$ are unit vectors $v_{i}^{T} v_{j} = \cos{\theta_{i, j}}$, we can bound the contribution of an edge $(i, j) \in E(G)$ by
\[\Prob[(i, j) \in cut(S)] = \frac{\theta_{i, j}}{\pi} \geq \alpha_{GW} \cdot \frac{1  v_{i}^{T} v_{j} }{2}\]where
\[\alpha_{GW} = \min_{\theta_{i, j} \in [0, \pi]} \lbrace \frac{2}{\pi} \cdot \frac{\theta_{i, j}}{ { 1  \cos(\theta_{i, j}) }} \rbrace \geq 0.878.\]Summing up the contributions over all edges, we arrive at the famous result
\[\Ex[f(S)] = \sum_{i, j} \Prob[(i, j) \in cut(S)] \geq \alpha_{GW} \cdot sdp(G).\]Dual problem
Let $L$ be the Laplacian matrix of a graph $G = (V, E)$. The dual problem of SDP relaxation is equivalent to finding maximum eigenvalue of $L$ with smallest added correction $u \in \mathbb{R}^{n}$, under constraint that $\sum_{i} u_{i} = 0$
\[\newcommand{\vect}[1]{\boldsymbol{#1}} \frac{n}{4} \min_{u: \vect{1}^{T} u = 0} \lambda_{\max}(L + diag(u))\]Setting $u = \vect{0}$ and by weak duality we get an upper bound
\[mc(G) \leq sdp(G) \leq \frac{n}{4} \lambda_{\max}(L)\]given earlier in (Mohar & Poljak, 1990). For 5cycle $C_{5}$, $\lambda_{\max} = \frac{1}{5}(5 + \sqrt{5})$, giving an upper bound
\[\frac{1}{2}(5 + \sqrt{5})/4 \geq 0.9 \cdot mc(C_{5}).\]This bound was studied in (Delorme & Poljak, 1993).
SoS relaxation
Now let $x \in \lbrace 0, 1 \rbrace^{n}$ and let $\mathcal{P}_{n}$ be a set of real valued polynomials $p(x)$ of degree at most $d/2$. Let
\[\tilde{\Ex}: \mathcal{P}_{n} \rightarrow \mathbb{R}\]be some operator over the probability distribution on $x$. We formulate the following optimization problem
\[\begin{align*} sos(G) := \ & \max_{\tilde{\Ex}} \ \tilde{\Ex}[ \sum_{i, j} (x_{i}  x_{j})^{2} ] \\ & \text{subject to: } \\[.4em] & \qquad \text{(1) $\tilde{\Ex}$ is linear} \qquad \text{(2) $\tilde{\Ex}[1] = 1$} \\[.4em] & \qquad \text{(3) $\tilde{\Ex}[p^2] \geq 0$} \qquad \, \, \, \text{(4) $\tilde{\Ex}[x_{i}^{2}p] = \tilde{\Ex}[x_{i}p]$} \\[.4em] & \qquad \forall p \in \mathcal{P}_{n} \end{align*}\]An operator $\tilde{\Ex}$ that realizes the maximum $sos(G)$ is called pseudoexpectation, because it only meets a subset of constraints (1)(3) required to be an actual expectation. The fourth constraint requires $x$ to be a vector $x \in \lbrace 0, 1 \rbrace^{n}$. Given a subset $S$ with maximum cut size $mc(G)$, let $\vect{a}$ be the indicator vector of $S$ and set $\tilde{\Ex} = \vect{a}$. Then $\tilde{\Ex}$ satisfies the constraints (1)(4) and achieves objective value $mc(G)$. In other words, given an expectation $a$, we can build a pseudoexpectation $\tilde{\Ex}$ just by setting $\tilde{\Ex} = \vect{a}$. Therefore $mc(G) \leq sos(G)$.
This framework is called SumofSquares hierarchy introduced by (Parrilo, 2000) and (Lasserre, 2001). Increasing the degree $d$, increases the size of the corresponding SDP problem. For $d = n$, the relaxation is exact. We can choose $d=2$ and show that we can get the same $\alpha_{GW}$approximation as before by rounding the solution of SoS relaxation.
Gaussian rounding
Let $\tilde{\Ex}$ be solution that realizes the maximum $sos(G)$. Select $\vect{y}$ to be a Gaussian vector with the mean $\mu = \tilde{\Ex}[x] = \frac{1}{2} \vect{1}$ and covariance matrix $\Sigma = \tilde{\Ex}[(x  \mu)(x  \mu)^{T}]$ and construct a subset $S = \lbrace i \in V : y_{i} \leq \frac{1}{2} \rbrace$. For each edge $(i, j) \in E(G)$, define
\[\rho_{i, j} = 4 \tilde{\Ex}[x_{i} x_{j}]  1.\]From $(s, t) \overset{\text{i.i.d.}}{\sim} N(0, I)$, setting
\[u = \rho_{i, j} s + \sqrt{1  \rho_{i, j}^{2}} t\]gives $\rho_{i, j} = \Ex[u s] = \cos(\theta_{i, j})$. Summing up the contributions, we can show that
\[\Ex[f(S)] = \sum_{i, j} \Prob[(i, j) \in cut(S)] \geq \alpha_{GW} \cdot sos(G)\]Generalizations
Given a nonnegative weight function on the edges, $w \in \mathbb{R}^{E}_{+}$, the cut size becomes
\[f(S) = \sum_{e \in \text{cut}(S)} w_e\]with no effect on analysis of approximation algorithms presented here. Given arbitrary weight function $w \in \mathbb{R}^{E}$, the analysis has to be adjusted but it is possible to derive a generalization of guarantees presented here.
Whether increasing degree from $d=2$ to $d=4$ of SoS Relaxation, also improves the approximation, still remains unresolved question.
Source code
Here is a simple implementation of GoemansWilliamson algorithm in Python:
import numpy as np
import cvxpy as cp
from scipy.linalg import sqrtm
def gw(n, edges):
'''GoemansWilliamson algorithm for MaxCut:
Given a graph G(V=[n], E=edges), returns a vector x \in {1, 1}^n
that corresponds to the chosen subset of vertices S of V. '''
## SDP Relaxation
X = cp.Variable((n, n), symmetric=True)
constraints = [X >> 0]
constraints += [
X[i, i] == 1 for i in range(n)
]
objective = sum( 0.5*(1  X[i, j]) for (i, j) in edges )
prob = cp.Problem(cp.Maximize(objective), constraints)
prob.solve()
## Hyperplane Rounding
Q = sqrtm(X.value).real
r = np.random.randn(n)
x = np.sign(Q @ r)
return x
def cut(x, edges):
'''Given a vector x \in {1, 1}^n and edges of a graph G(V=[n], E=edges),
returns the edges in cut(S) for the subset of vertices S of V represented by x.'''
xcut = []
for i, j in edges:
if np.sign(x[i]*x[j]) < 0:
xcut.append((i, j))
return xcut
To solve an SDP problem it uses CVXPY (Diamond & Boyd, Version 1.2).
Algorithm is randomized and returns a random cut, but guarantees that on average: cut size >= 0.878 * maximum cut size
. For the trivial example of a cycle on 5 vertices, the chosen subset and corresponding cut may vary, but the return cut will always be of size 4:
## Define a cycle on 5 vertices
n = 5
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (0, 4)]
## Run GoemansWilliamson algorithm
x = gw(n, edges)
## Find edges in the cut
xcut = cut(x, edges)
print('Chosen subset: %s' % np.where(x == 1))
print('Cut size: %i' % len(xcut) )
print('Edges of the cut: %s' % xcut )
# Chosen subset: [1 4]
# Cut size: 4
# Edges of the cut: [(0, 1), (1, 2), (3, 4), (0, 4)]
References
 Goemans, M. X., & Williamson, D. P. (1995). Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42(6), 1115–1145. https://doi.org/10.1145/227683.227684
 Karp, R. M. (1972). Reducibility among Combinatorial Problems. In R. E. Miller, J. W. Thatcher, & J. D. Bohlinger (Eds.), Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 2022, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department (pp. 85–103). Springer US. https://doi.org/10.1007/9781468420012_9
 Erdős, P. (1967). On bipartite subgraphs of a graph. Matematika Lapok, 18, 283–288.
 Michalek, M., & Sturmfels, B. (2021). Invitation to nonlinear algebra, Chapter 12: Semidefinite Programming. American Mathematical Society. https://www.math.unikonstanz.de/~michalek/june26.pdf
 Mohar, B., & Poljak, S. (1990). Eigenvalues and the maxcut problem. Czechoslovak Mathematical Journal, 40(2), 343–352. http://eudml.org/doc/13856
 Delorme, C., & Poljak, S. (1993). Laplacian Eigenvalues and the Maximum Cut Problem. Math. Program., 62(1–3), 557–574.
 Parrilo, P. A. (2000). Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization [PhD thesis, California Institute of Technology]. https://doi.org/10.7907/2K6YCH43
 Lasserre, J. B. (2001). Global Optimization with Polynomials and the Problem of Moments. SIAM Journal on Optimization, 11(3), 796–817. https://doi.org/10.1137/S1052623400366802
 Diamond, & Boyd. (Version 1.2). CVXPY: A Pythonembedded modeling language for convex optimization. https://www.cvxpy.org/