A 2-approximation algorithm for minimum vertex cover? 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.
 A: 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|$.
A: Here is a simpler analysis, with more of a combinatorial flavor (compared to the probabilistic approach by Amit), which Ajit Diwan told me:
"As Amit Rajaraman has said, view this
as picking an edge, selecting one of its endpoints randomly and deleting all
edges incident with it.  Suppose the minimum vertex cover of the current
graph is $k$. With probability $1/2$ it reduces to $k-1$ after one step, or it
remains the same with probability half. The algorithm stops when it reduces
to $0$.  The expected number of steps for this is $2k$."
In some more detail:
Let $G$ be the input graph to our algorithm $\mathcal{A}$. After one step, let the two possible graphs be $G_1$ and $G_2$. Let $h(G)$ be a random variable that denotes the number of steps for which $\mathcal{A}$ runs on input $G$. It's not very difficult to see that
$$\mathbb{E}[h(G)] = 1+ \frac{1}{2}\mathbb{E}[h(G_1)] + \frac{1}{2}\mathbb{E}[h(G_2)]$$
Now, we can do a two-fold induction on $n$-inside-$k$ to prove that $$\mathbb{E}[h(G)] \leq 2k .$$
This approach looks useful for proving a bound on the approximation factor for other randomized graph algorithms as well.
