Under Construction (GVC) MINIMUM GENERALIZED VERTEX COVER Instance: Graph G=(V,E), for each vertex v in V a weight W(v)>=0; and for each edge e in E a "penalty" weight W(e)>=0; Solution: A subset C of V. Measure : W(C)+W(E(V-C)) i.e: Sum {W(v): v in C} + Sum {W(e): e is not "covered" by C} +-----------------------------------------------------------------+ | The "Local-Ratio Theorem" (oriented for VC) | +-----------------------------------------------------------------+ | If C is 2-approximation GVC w.r.t the weight function W1 | | and C is 2-approximation GVC w.r.t the weight function W2 | | then C is 2-approximation GVC w.r.t the weight function W1+W2 | +-----------------------------------------------------------------+ Let e=(v,u) be any edge s.t. epsilon>0 where: epsilon = Min(W(v),W(u),W(e)) define W1(v) = W1(u) = W1(e) = epsilon and 0 for all others. Q1: All subsets are 2-approximations w.r.t W1. Why? Hint: prove that for any C, epsilon <= W1(C) <= 2*epsilon The algorithm: iteratively subtract W1 as above. Induction hyp. implies that reclusive call with W2=W-W1 would return a set C which is 2-approximation w.r.t. W2. C (and any set) is 2-approximation w.r.t. W1 (see Q1). By the "Local-Ratio Theorem" C is 2-approximation w.r.t. W=W1+W2. Q2: What to do with zero weight vertices? Q3: What to do with zero weight edge? Hence: The following linear time algorithm is 2-approximation. +-------------------------------------+ | Algorithm Bar-Yehuda&Rawitz(G,W) | +-------------------------------------+ | for each edge e=(v,u) | | epsilon = Min(W(v),W(u),W(e) | | W(v) -= epsilon | | W(u) -= epsilon | | W(e) -= epsilon | | return {v: W(v)=0} | +-------------------------------------+