$\backslash ((6\backslash$mathrm$\{$pts$\})\backslash$quad $\backslash )2.$ Randomized max$-$cut.

In this problem, all graphs are undirected and have no self$-$loop, i$.$e$.,$ there is no edge from a vertex to itself. For a cut $\backslash ($ S $\backslash$subseteq V $\backslash )$ in a graph $\backslash ($ G$=($V$,$ E$)\backslash ),$ let $\backslash ($ C$($S$)\backslash$subseteq E $\backslash )$ denote the subset of edges "crossing" the cut, i$.$e$.,$ those that have exactly one endpoint in $\backslash ($ S $\backslash ).$ The size of the cut is then $\backslash (|$C$($S$)|\backslash ).$ Consider the following randomized algorithm that outputs a cut in a given graph $\backslash ($ G$=($V$,$ E$)\backslash ).$

$```$

initialize S$=\backslash$emptyset

for all v$\backslash$inV do

put v into S with probability $1/2,$ independently of all others

return S

$```$

Define suitable indicator variables and use linearity of expectation to prove that in expectation, the above algorithm obtains a $1/2-$approximation for MaxCut. That is$,$ the expected size of the output cut is at least half the size of a maximum cut.

This algorithm is interesting because it achieves the same approximation factor $($in expectation$)$ as the local$-$search algorithm from lecture, but it is much simpler and faster!