= Conditional expectation cut formula
{title2=$q(P)=f(P)+u(P)/2$}
For any partial assignment $P$, let $f(P)$ count <edges> whose two endpoints are already fixed on opposite sides, and let $u(P)$ count <edges> with at least one unassigned endpoint. Under the remaining <independent> fair <bits>,
$$
q(P)=\mathbb E[C\mid P]=f(P)+\frac{u(P)}2.
$$
An <edge> with fixed equal labels contributes zero; fixed unequal labels contribute one. If one endpoint is unassigned, its fair <bit> disagrees with the fixed label with <probability> $1/2$. If both endpoints are unassigned, their <independent> fair <bits> disagree with <probability> $1/2$ as well. Count each unresolved <edge> once, even when both endpoints are unassigned.
Process <vertices> in a fixed order. Evaluate the <conditional expectation cut formula> after setting the next label to zero and after setting it to one; retain the larger value, choosing zero on ties. The <conditional expectation choice invariant> ensures the final <cut of a graph> has size at least $m/2$. This is a deterministic <approximation algorithm> for <maximum cut>.<CS 4820: Algorithms, Spring 2011/Lecture notes on randomized approximation algorithms>[CS 4820: Algorithms, Spring 2011; Cornell CS 4820, Lecture notes on randomized approximation algorithms, 2 May 2011, §1.1.2, printed pp. 2–3: conditional expectations, Algorithms 1–2 and the half-total-edge-weight guarantee; no individual byline stated]{ref}
Back to article page
