Reduction to Set Cover

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 .

Lemma (reduction to Set Cover).

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:

Corollary.

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 .

Corollary.

That greedy algorithm returns a cover of cost at most , which is at most .

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).