Under Construction (PSC) MINIMUM PARTIAL SET COVER (hypergraph formulation) Instance: Hyper graph G=(V,E), for each vertex v in V a weight W(v)>=0; a number t>0; Solution: A t-set-cover for G, (t-SC) i.e., a subset C of V such that, at lease t hyper-edges are covered by C ( |E(C)| >= t) Measure : W(C) (i.e. Sum {W(v): v in C}) Define d to be the maximum edge cardinality. +------------------------------------------------------------------+ | The "Local-Ratio Theorem" (oriented for PSC) | +------------------------------------------------------------------+ | If C is d-approximation t-SC w.r.t the weight function W1 | | and C is d-approximation t-SC w.r.t the weight function W2 | | then C is d-approximation t-SC w.r.t the weight function W1+W2 | +------------------------------------------------------------------+ Our objective is to find a MINIMAL-t-SC C, i.e. C is an t-SC, but for each v in C: C-{v} is not t-SC. Define W1 to be epsilon HOMOGENEOUS, i.e. for all v in V: W1(v) = epsilon*Min(t,degree(v)) Q1: Every MINIMAL-FVS is d-approximations w.r.t W1. Why? A1: See my paper from SODA99. +-------------------------------------------------------------------+ | Algorithm Partial_SC (G=(V,E),W,t) | +-------------------------------------------------------------------+ | If |E| 0 and C-{x} is t-SC for G | | then C=C-{x} | | Return C | +-------------------------------------------------------------------+ In the SODA99 paper, we generalize the problems so that the hyper-graph edges are not of "unit length" i.e. each edge have a "length" so we need length(E(C))>=t.