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|