So this algorithm perform the following very easy steps: for any variable the algorithm just flip a coin, if the result is head it keeps the value true to the variable, otherwise it keeps the value false to the variable.
So we are giving the variable true to a variable with probability 1/2,
that the expected
Surprisingly it can be shown that by simple calculation the expected performance ratio of the solution computed by this algorithm is bounded by 2.
