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 {\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.

Lemma (reduction to Set Cover).

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:

Corollary.

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

Corollary.

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.

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