Conditional expectation yields a deterministic half-approximation for Max-Cut

Let $X:={\sum }_{e\in E}{X}_e$ be the number of crossing edges, where $X_e$ is the indicator that the endpoints of $e$ lie on different sides. For a partial assignment $a=(a_1,\dots ,a_k)$ of the first $k$ bits, define the conditional expectation $\mathbb{E}[X\mid a]$ as the average of $X$ over the $2^{n-k}$ equally weighted completions. The closed form is $\mathbb{E}[X\mid a]=A(a)+\frac{1}{2}B(a)$, where $A(a)$ counts the edges whose two endpoints are among the fixed vertices and which cross under $a$, and $B(a)$ counts the edges with at least one unfixed endpoint: a fully fixed edge contributes its crossing indicator, an edge with exactly one fixed endpoint crosses for exactly one of the two equally likely values of the free bit, an edge with two unfixed endpoints crosses for exactly two of the four equally likely pairs of free bits, and [F3] sums these contributions, the edges being finitely many.

For any $k<n$ and any $a$, the completions of $a$ split into those with $b_{k+1}=0$ and those with $b_{k+1}=1$, two equally weighted families of equal size, so $\mathbb{E}[X\mid a]=\frac{1}{2}(\mathbb{E}[X\mid a,0]+\mathbb{E}[X\mid a,1])$. Hence at least one of the two one-bit extensions has conditional expectation at least $\mathbb{E}[X\mid a]$, and the maximizer is at least the current value.

Define the algorithm: start with the empty assignment $a$; for $k=0,1,\dots ,n-1$ compute the two numbers $\mathbb{E}[X\mid a,0]$ and $\mathbb{E}[X\mid a,1]$ from the closed form of step 1.1, each a sum over the $m$ edges, and extend $a$ by $b_{k+1}=0$ if $\mathbb{E}[X\mid a,0]\ge \mathbb{E}[X\mid a,1]$ and by $b_{k+1}=1$ otherwise; return the resulting cut. By step 2.1 the conditional expectation does not decrease at any choice, so the nondecreasing sequence $\mathbb{E}[X\mid \mathrm{\varnothing }]=m\mathrm{/}2,\mathbb{E}[X\mid b_1],\dots ,\mathbb{E}[X\mid b_1,\dots ,b_n]=X$ ends at the actual cut size of the returned placement, giving $X\ge m\mathrm{/}2$.

The algorithm is deterministic after the fixed tie rule $b_{k+1}=0$ and the fixed vertex order, and it runs in polynomial time: $n$ rounds with two closed-form evaluations of $O(m)$ exact rational operations each, all comparisons of rationals with polynomially bounded bit lengths. By step 3.1 and [F1], the returned feasible cut satisfies $X\ge m\mathrm{/}2\ge \frac{1}{2}{\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}$; when $m=0$ both values are zero. By [F2] this is a deterministic polynomial-time $1\mathrm{/}2$-approximation for Max-Cut.