Consider the following (randomized) algorithm for the minimum vertex cover problem:
We go over all the edges and assign $-$ or $1$ values to its vertices (here $-$ means we haven't decided the assignment of this vertex yet). In the end we declare all the $1$-valued vertices as our approximate min vertex cover.
More formally, start with $f(v) = -$ for all $v$ in $V$. Given a graph as input, there is a natural total ordering of its edges (we can consider any total ordering of the edges, not necessarily the "natural" one). We go over each edge in this order. When we are looking at an edge $\{u,v\}$, if $f(u) = 1$ or $f(v) = 1$ as a result of some previous assignment, we continue to the next edge. Else, we assign $(f(u), f(v)) = (-,1)$ or $(1,-)$ with equal probability. Iterate over all edges like this. Output $f^{-1}(1)$ as the min vertex cover.
Clearly $\mathbb{E}[|f^{-1}(1)|] \geq $ size of a min vertex cover. I couldn't prove that $\mathbb{E}[|f^{-1}(1)|] \leq $ twice the size of a min vertex cover. But, I couldn't disprove it either. Can you find a proof or a counterexample?
Note that this algorithm cannot be a $(2 – \epsilon)$– approximation algorithm for any constant $\epsilon > 0$. The star graph (a single vertex $0$ connceted to vertices $1,\cdots,n$ and no other edge) shows this.
Best Answer
Your algorithm is indeed a $2$-approximation algorithm.
Let me rephrase the algorithm slightly. Instead of iterating over every edge, instead remove all edges that are connected to a vertex when we add a new vertex to our set of vertices labelled $1$s. That is, at each step of the algorithm, we choose an arbitrary edge in the (remaining) graph, add one of its endpoints to the set with equal probability for each endpoint, and then remove all edges that are incident on this vertex.
Note that phrased in this way, the size of the vertex cover output by the algorithm is precisely the number of edges we choose.
Let $C$ be a smallest vertex cover.
Split the edge set into $|C|$ parts, assigning each edge to a vertex in $C$ it is incident on. Consider some vertex $v \in C$. What is the expected number of $v$-edges (edges assigned to $v$) I choose before all $v$-edges are covered by the set? Clearly, for each such edge I choose, I add $v$ itself with probability $1/2$ (in which case all $v$-edges are immediately covered), so the number is at most $2$.
Let me write the above argument a bit more formally. Let $k_v$ be the random variable indicating the number of $v$-edges I choose. I have $$ \Pr[ k_v=r \mid k_v \ge r] \ge \frac{1}{2}. $$ Indeed, when I choose the $r$th $v$-edge, I pick $v$ itself with probability $1/2$. Therefore, $$ \Pr[ k_v \ge r+1 \mid k_v \ge r] \le \frac{1}{2} $$ and so, $$ \Pr[ k_v \ge r+1 ] \le \frac{1}{2} \Pr[ k_v \ge r ]. $$ Consequently, for any $r \ge 1$, $\Pr[k_v \ge r] \le 2^{-r+1} \Pr[k_v \ge 1] \le 2^{-r+1}$, so $$ \mathbb{E}[k_v] = \sum_{r=1}^{\infty} \Pr[k_v \ge r] \le \sum_{r=1}^{\infty} 2^{-r+1} = 2. $$
Consequently, the total number of edges I choose before all edges are covered is, in expectation, at most $2|C|$.