Derandomization of vertex cover algorithm I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set: 

Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.

Add to $B_0$ all isolated vertices, i.e. the ones without any incident edges.

For every edge $e$ in $e_1,e_2,...,e_m$
if both endpoints of e are not contained in $B_0$, then
flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.

I have already proved that this algorithm has $E[|B_0|] \le 2|OPT|$.

Now I don't know how to apply the method of conditional expectations (defined here) to derandomize the algorithm in order to show that we can't obtain an efficient deterministic version and that gives the same result of the expected value found previously.
Can you show me to do this?
First, let us repeat the analysis of the algorithm.

Fix some optimal vertex cover OPT, with cost $O$.

Let $S$ be the cost of the vertex cover produced by the algorithm.

Let $A_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex belonging to OPT", and let $A = \sum_e A_e$.

Let $B_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex not belonging to OPT", and let $B = \sum_e B_e$.

Thus $S = A+B$ and $A \leq O$.

The idea of the analysis is that $\Pr[B_e] \leq \Pr[A_e]$. To see this, consider what happens when vertex $e$ is considered. If $e$ is already covered by vertices already chosen, then $A_e = B_e = 0$. If both endpoints of $e$ belong to OPT, then $A_e = 1$ and $B_e = 0$. Otherwise, $\Pr[A_e] = \Pr[B_e] = 1/2$. In all cases, $\Pr[B_e] \leq \Pr[A_e]$.

Since $\Pr[B_e] \leq \Pr[A_e]$, we have $\mathbb{E}[B] \leq \mathbb{E}[A]$. Therefore
$$
\mathbb{E}[S] = \mathbb{E}[A+B] \leq 2\mathbb{E}[A] \leq 2O.
$$

How would we apply the method of conditional expectations? Here are two options:


Given the choice of which endpoint is taken, compute the expected value of $S$. If $z \in \{x,y\}$ was chosen, then we remove all edges adjacent to $z$, and then run the algorithm as usual. This reduces the problem to computing $\mathbb{E}[S]$, which is the expected number of edges which are not covered when their time comes. It's not so clear how to compute $\mathbb{E}[S]$.
The same, but instead of computed $\mathbb{E}[S]$ exactly, compute an approximation which is good enough to obtain a 2-approximation. Let $O_z$ be the optimum solution after removing all edges adjacent to $z$. Then
$$
\mathbb{E}[S \mid x] \leq 1 + 2O_x, \quad
\mathbb{E}[S \mid y] \leq 1 + 2O_y.
$$
If $x$ belongs to OPT then $O_x = O-1$, and otherwise $O_x \leq O$. Thus the average of both bounds is at most
$$
\frac{1+2(O-1)+1+2O}{2} = 2O,
$$
since at least one of $x,y$ belongs to OPT. Therefore, if we choose the vertex that minimizes $O_x,O_y$, then the resulting algorithm will produce a 2-approximation. Unfortunately, it's not clear how to compute $O_x,O_y$ (indeed, this ought to be hard).


In summary, it's not so clear how to apply the method of conditional expectations.