SP2 MAXIMUM SET PACKING Instance: Collection E of finite sets. Each set e in E has a weight w(e)>=0. Solution: A set packing (SP), i.e., a collection M of disjoint sets of E. Measure : Weight of the set packing: W(P) (=Sum {W(e): e in P}). Comment : Also called Maximum Hypergraph Matching. Define : k=max{|e|: e in E} Good News: Approximable within k-1+\varepsilon for any \varepsilon>0 [Arkin Hassin 97 - See Compendium SP2] The k-approximation presented here is to ilustrate the use Of the Local-Ratio techniqe on a Maximum sum problem +-----------------------------------------------------------------+ | The "Local-Ratio Theorem" (oriented for MSP) | +-----------------------------------------------------------------+ | If M is k-approximation SP w.r.t the weight function W1 | | and M is k-approximation SP w.r.t the weight function W2 | | then M is k-approximation SP w.r.t the weight function W1+W2 | +-----------------------------------------------------------------+ Our objective is to find a MAXIMAL-SP M, i.e. M is an SP, but for each e in E-M: M+{v} is not SP. Define W1 to be epsilon HOMOGENEOUS, i.e. for all e in E: W1(e) = epsilon Q1: Every MAXIMAL-SP is k-approximations w.r.t W1. Why? Q2: We Can assume that all setes in E are non empty. Why? +-------------------------------------------------------------------+ | Algorithm SetPacking (E,W) | +-------------------------------------------------------------------+ | If all sets in E are disjoints (hyper matching) return E | | {Local ratio step:} | | Let epsilon = min_{e in E} W(e) | | Define W : forall_{e in E} W1(e) = epsilon | | M = SetPacking (E,W-W1) | | {Make it "Maximal" loop:} | | for each e in M, if W1(e) > 0 and M+{e} is SP for E | | then M=M+{e} | | Return M | +-------------------------------------------------------------------+ p.s. A simpler weight function. Let e' be any hyper-edge (can select one with min cardinality). define for each hyper-edge e: W1(e) = epsilon iff e intersects e' Clearly, for maximal matching M: epsilon <= W1(M) <= epsilon*|e|