Consider the following algorithm for the weighted vertex cover problem. For each vertex v, t(v) is initialized to its weight, and when t(v) drops to 0, v is picked in the cover. c(e) is the amount charged to edge e Algorithm 2.17 1. Initialization: C v V , t(v) w(v) e E, c(e) 0 2. While C is not a vertex cover do: Pick an uncovered edge, say (u, v). Let m = min(t(u), t(v)). t(u) t(u) m t(v) t(v) m c(u, v) m Include in C all vertices having t(v) = 0. 3. Output C. Show that this is a factor 2 approximation algorithm. Hint: Show that the total amount charged to edges is a lower bound on OPT and that the weight of cover C is at most twice the total amount charged to edges.