= Conditional expectations algorithm cost
Directly scanning all $m$ <edges> to evaluate each child of each of $n$ choices takes $O(nm+n)$ elementary operations, in <Big O notation>. There is a faster implementation. When assigning <vertex> $v$, let $d_0$ and $d_1$ count its already assigned <graph neighbours> labelled zero and one. Contributions from <edges> not incident to $v$ are unchanged, and contributions from <edges> to unassigned <graph neighbours> stay $1/2$ for either choice. Therefore
$$
q(P,v=0)-q(P,v=1)=d_1-d_0.
$$
Choose zero if $d_1\geq d_0$, otherwise one: put $v$ on the side with fewer already assigned <graph neighbours>. With <adjacency lists>, scanning each <vertex>'s list once costs $O(n+m)$ operations overall and uses $O(n+m)$ storage including the <graph>. These bounds count operations on labels and counters that fit in machine words of $O(\log(n+m+2))$ <bits>. Multiplying the <conditional expectation cut formula> by two also permits exact integer comparisons without rounding.
If $\operatorname{OPT}$ is the size of a <maximum cut>, then $\operatorname{OPT}\leq m$. The constructed <cut of a graph> thus has size at least $m/2\geq\operatorname{OPT}/2$, an <approximation ratio> of $1/2$ in the maximization convention. The five-versus-six example illustrates the gap between this guarantee and exact optimization.
For a general <randomized algorithm>, the averaging proof alone does not establish efficient <derandomization>. One needs a polynomial number of commitments, an efficient way to find a suitable child at each step, and manageable representations and evaluation costs for the relevant <conditional expectations>. Those evaluations can themselves be hard. Enumerating all completions verifies this small example, but would take exponentially many assignments as $n$ grows. The <polynomial-time algorithm> here comes from the local <conditional expectation cut formula>, not from that enumeration.
Back to article page
