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 = \emptyset$.
- 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$ not contained in $B_0$, then
- flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.
How can I prove that, for every constant $c \geq 1$, the algorithm might produce a $B_0$ with $|B_0 | \ge c|OPT|$?