(SC) MINIMUM SET COVER (hypergraph formulation) Instance: Hyper graph G=(V,E), for each vertex v in V a weight W(v)>=0; Solution: A set cover for G, i.e., a subset C of V such that, for each edge (v,u) in E, at least one of u and v are in C; Measure : W(C) (i.e. Sum {W(v): v in C}) Define k=Max{|e| : e in E} +----------------------------------------------------------------+ | The "Local-Ratio Theorem" (oriented for SC) | +----------------------------------------------------------------+ | If C is k-approximation SC w.r.t the weight function W1 | | and C is k-approximation SC w.r.t the weight function W2 | | then C is k-approximation SC w.r.t the weight function W1+W2 | +----------------------------------------------------------------+ Let {v1,v2,...vk} be any hyper-edge s.t. epsilon>0 where: epsilon = Min(W(v1),W(v2),...,W(vk)) define W1(v1)=W1(v2)=...=W1(vk)=epsilon and 0 for all others. Q1: All set covers are k-approximations w.r.t W1. Why? The algorithm: iteratively subtract W1 as above. Induction hyp. implies that reclusive call with W2=W-W1 would return a set cover C which is d-approximation w.r.t. W2. (Where d is an upper bound on the edge cardinality) C (and any set cover) is d-approximation w.r.t. W1 (see Q1). By the "Local-Ratio Theorem" C is d-approximation w.r.t. W=W1+W2. Q2: What to do with zero weight vertices? Hence: The following linear time algorithm is d-approximation. +-------------------------------------------------+ | Algorithm Bar-Yehuda&Even(G,W) | +-------------------------------------------------+ | for each edge e in E | | Let epsilon = Min{W(v): v endpoint of E} | | W(v) -= epsilon for all v endpoint of E | | return {v: W(v)=0} | +-------------------------------------------------+