Unconstrained Set Multicover reduces to Set Cover.
Unconstrained Set Multicover has an approximation-preserving reduction to Set Cover that also preserves maximum set size. This reduction (and previous results on Set Cover) imply that a localized rounding scheme and a greedy algorithm both give {\rm H}(\max _ s |s|)-approximation.
The reduction
Here is the reduction. Fix any instance {\cal I} of Unconstrained Set Multicover. Replace each element e with d_ e duplicates of e. Replace each set s with \prod _{e\in s} d_ e copies of s, where each copy contains exactly one of the duplicates of each element of e. This gives an instance {\cal I}’ of Set Cover. The size of each copy of s is equal to the size of s.
For every unconstrained Set Multicover instance {\cal I}, the above Set Cover instance {\cal I}’ has the same maximum set size and is equivalent, in that the solutions to {\cal I} correspond to the solutions to {\cal I}’, and the correspondence preserves feasibility, cost, and integrality.
Rounding scheme and greedy algorithm via reduction
The corollaries below follow from the reduction:
The localized rounding scheme for unconstrained Set Multicover returns a cover of expected cost at most \sum _ s {\rm H}(|s|) c_ s x_ s, which is at most {\rm H}(\max _ s |s|) ~ c\cdot x.
Consider the following greedy algorithm for unconstrained Set Multicover: Start with each \tilde x_ s = 0. At each iteration, choose s minimizing the ratio of c_ s to the number of not-yet-satisfied elements in s, then increment \tilde{x_ s}.
That greedy algorithm returns a cover of cost at most \sum _ s{\rm H}(|s|) c_ s x_ s, which is at most {\rm H}(\max _ s |s|) ~ c\cdot x.
Related
Questions for later
Generalize to constrained Set Multicover (where the solution must take each set s at most once). (The Knapsack-cover inequalities give a reduction, but it increases \max _ s |s|.) Aim for {\rm H}(\max _ s |s|)-approximation (matching Wolsey).
Bibliography
[1] | V. Vazirani. Approximation Algorithms. Springer Verlag, 2003. |