4. This question considers randomized algorithms for approximating vertex-cover problems. (a) Consider the following probability experiment: There is a fixed set of k distinct items. The experiment proceeds in a sequence of rounds. In each round, with probability at least 1/2 (and independently of all other rounds), some arbitrary item that was not previously chosen is chosen. (Otherwise, nothing is chosen in this round.) Once every item has been chosen, the experiment ends. Let R be the random variable denoting the number of rounds until the experiment ends. Prove that E[R] 2k. Hint: for i = 1,..., k, let R; be the random variable denoting the number of rounds after the (1)st chosen item and until the jth chosen item (inclusive). What is the relationship between R and the R? What is an upper bound on E[R;]? (b) Prove that the following randomized algorithm outputs a 2-approximation, in expecta- tion, for the minimum vertex cover problem. = Hint: let C* {v1, v} be some minimum vertex cover in the input graph. Show how a run of the algorithm corresponds to a (complete or partial) run of the experiment from the previous part with the v; as the items, and use this to bound the expected size of the output C. (Recall that the "double cover algorithm deterministically gives a 2-approximation to vertex cover, but the following parts will show that a randomized approach is more versatile.) 1: function RANDOMSINGLECOVER(G = (V,E)) 2: 3: 4: 5: C+0 while there is some edge e = (u, v) that is not covered by C do Add exactly one of u or v to C, each with probability 1/2 return C (d) Optional extra credit. Describe and analyze an efficient randomized algorithm that, in expectation, outputs a 2-approximation for the minimum-weight vertex cover problem. Hint: Consider the algorithm from part (b), but instead of selecting each vertex with probability 1/2, use an appropriate bias.