Several entries on unconstrained Set Multicover.
Entries on unconstrained Set Multicover
Reduction to Set Cover
Unconstrained Set Multicover has an approximationpreserving 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.Unconstrained Set Multicover reduces to Set Cover.
A greedy algorithm for unconstrained Set Multicover
This example illustrates the use of “Wald’s equation for dependent decrements”. The rounding scheme and algorithm can be exponentially slow. In a later example, we speed it up using nonuniform increments.{\rm H}(n)approximation for unconstrained Set Multicover by oblivious randomized rounding.
Nonuniform increments
The algorithm in the previous note can be exponentially slow. Here we use nonuniform increments to give a faster rounding scheme and algorithm.Applying nonuniform increments to unconstrained Set Multicover.
Questions for later
Generalize results here to constrained Set Multicover (where the solution must take each set s at most once). Aim for {\rm H}(\max _ s s)approximation (matching Wolsey).
Related

[1, Exercise 13.4.1]
Bibliography
[1]  V. Vazirani. Approximation Algorithms. Springer Verlag, 2003. 
MathJax is loading, equations are not yet displayed...