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 -approximation.
The reduction
Here is the reduction. Fix any instance of Unconstrained Set Multicover. Replace each element with duplicates of . Replace each set with copies of , where each copy contains exactly one of the duplicates of each element of . This gives an instance of Set Cover. The size of each copy of is equal to the size of .
For every unconstrained Set Multicover instance , the above Set Cover instance has the same maximum set size and is equivalent, in that the solutions to correspond to the solutions to , 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 , which is at most .
Consider the following greedy algorithm for unconstrained Set Multicover: Start with each . At each iteration, choose minimizing the ratio of to the number of not-yet-satisfied elements in , then increment .
That greedy algorithm returns a cover of cost at most , which is at most .
Related
Questions for later
Generalize to constrained Set Multicover (where the solution must take each set at most once). (The Knapsack-cover inequalities give a reduction, but it increases .) Aim for -approximation (matching Wolsey).
Bibliography
| [1] | V. Vazirani. Approximation Algorithms. Springer Verlag, 2003. |