(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} |
+-------------------------------------------------+