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|