Given an undirected graph G=(V,E)G = (V, E), the maximum cut problem asks for a subset S⊂VS \subset V that maximizes the number of edges which cross SS, i.e.,

S=arg⁡max⁡S′⊂Sδ(S), S = \arg \max_{S' \subset S} \delta(S),

where δ(S)=∣{ (i,j) ∣ (i,j)∈E∧i∈S,j∉S}∣\delta(S) = |\{ \ (i, j) \ \mid \ (i, j) \in E \wedge i \in S, j \notin S\}|.

Programming Formulation

To solve the problem, we assign each vertex i∈Vi \in V a binary indicator xi∈{−1,1}x_i \in \{-1, 1\} for the event that ii belongs to SS. WLOG, we assume that i∈Si \in S if xi=1x_i = 1. The value of δ(S)\delta(S) can be written as

δ(S)=∑(i,j)∈E1−xixj2 \delta(S) = \sum_{(i,j) \in E} \frac{1 - x_i x_j}{2}

Its correctness can be verified as follows:

  1. if i,j∈Vi, j \in V belongs to the same partition, i.e, i,j∈Si, j \in S or i,j∈V−Si, j \in V - S, then xixj=1x_i x_j = 1 and (1−xixj)/2=0(1 - x_i x_j) / 2 = 0
  2. Otherwise, xixj=−1x_i x_j = -1 and (1−xixj)/2=1(1 - x_i x_j) / {2} = 1.

Convex Relaxation

We consider a relaxation of the above programming:

max⁡∑(i,j)∈E1−xiTxj2s.t.,xiTxi=1∀i∈Vxi∈Rn∀i∈V \begin{array}{lrl} \max &\sum_{(i,j) \in E} \frac{1 - x_i^T x_j}{2} \\ \text{s.t.}, & x_i^T x_i = 1 &\forall i \in V \\ & x_i \in \mathbb{R}^n &\forall i \in V \end{array}

Note that this can be transformed into a convex optimization:

max⁡∑(i,j)∈E1−yi,j2s.t.,yi,i=1∀i∈Vyi,j=yj,i∀i,j∈VY=(yi,j)≽0 \begin{aligned} &&\max &&\sum_{(i,j) \in E} \frac{1 - y_{i,j}}{2} &&\\ &&s.t., && y_{i,i} = 1 &&\forall i \in V \\ && && y_{i,j} = y_{j,i} &&\forall i, j \in V \\ && && Y = (y_{i,j}) \succcurlyeq 0 \end{aligned}

The above problem can be solved within ϵ\epsilon additive error in polynomial time in terms of input size and log⁡1/ϵ\log 1/\epsilon.

Rounding

To round the fractional solution to integral solution, we take a random unit vector v∈Rnv \in \mathbb{R}^n. For each vertex ii, if vTxi≥0v^T x_i \ge 0 we set xi′=1x_i' = 1 otherwise we set xi′=0x_i' = 0. For any pair i,j∈Vi, j \in V, if xi=xjx_i = x_j, then we set θi,j=0\theta_{i,j} = 0. Otherwise, consider the two dimensional subspace in Rn\mathbb{R}^n spanned by xix_i and xjx_j. Denote the angle between xix_i and xjx_j as θi,j\theta_{i,j}. We have

θi,j=arccos⁡xiTxj. \theta_{i, j} = \arccos x_i^T x_j.

Notice that

∑(i,j)∈E1−xixj2=∑(i,j)∈E1−cos⁡θi,j2. \sum_{(i,j) \in E} \frac{1 - x_i x_j}{2} = \sum_{(i,j) \in E} \frac{1 - \cos \theta_{i,j}}{2}.

Furthermore, the probability that xi′x_i' and xj′x_j' are assigned different values is given by θi,j/π\theta_{i,j} / \pi. By linearity of expectation, the expected cut value is

E[∑(i,j)∈E1−xi′xj′2]=∑(i,j)∈Eθi,jπ \mathbb{E} \left[ \sum_{(i,j) \in E} \frac{1 - x_i' x_j'}{2} \right] = \sum_{(i,j) \in E} \frac{\theta_{i,j}}{\pi}

As max⁡0≤θ≤ππθ1−cos⁡θ2≈1.138\max_{0 \le \theta \le \pi} \frac{\pi}{\theta}\frac{1 - \cos \theta}{2} \approx 1.138, E[∑(i,j)∈E1−xi′xj′2]\mathbb{E} \left[\sum_{(i,j) \in E} \frac{1 - x_i' x_j'}{2} \right] is greater approximately 1/1.138=0.878⋅∑(i,j)∈E1−xixj21/1.138 = 0.878 \cdot \sum_{(i,j) \in E} \frac{1 - x_i x_j}{2}.