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.

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