# A greedy algorithm for unconstrained Set Multicover

-approximation for unconstrained Set Multicover by oblivious randomized rounding.

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 non-uniform increments.

# The rounding scheme

Fix an instance of unconstrained Set Multicover. Here is the rounding scheme:

 input: fractional multicover output: multicover 1. Initialize for every set . 2. Repeat until every element is covered: 3. Sample a set from the distribution . 4. Increase by 1. 5. Return .
Lemma (existence proof).

Fix a problem instance. Let be the number of elements. The set cover returned by the rounding scheme has expected cost at most .

# Applying the method of conditional probabilities

Lemma (algorithm).

Applying the method of conditional probabilities to the existence proof yields the algorithm below:

 input: Set Multicover instance output: multicover 1. Initialize for every set . 2. Repeat until every element is covered: 3. Choose a set to maximize . 4. Increase by 1. 5. Return .

This greedy algorithm differs from the one following from the reduction to Set Cover, in that, in choosing , it gives each element weight instead of .

This performance guarantee follows as a corollary:

Theorem.

The algorithm above returns a multicover of cost at most , where is the minimum cost of any fractional multicover.

# Localizing gives {\rm H}(\max _ s|s|)-approximation

We note without recording the proof that localizing the above rounding scheme improves the approximation ratio of the rounding scheme and algorithm to . The localized greedy algorithm is not the one directly above. It is the same as the algorithm from the reduction (it chooses the set in each iteration to maximize the number of not-yet-satisfied elements in divided by .)

This approach generalizes to unconstrained Multiset Multicover (where each set covers element with a given integer multiplicity ). The localized analysis gives approximation ratio . The same result can be obtained by applying Wolsey’s generalization of the Set-Cover algorithm [1, 3], using the following submodular constraint for : that . That approach proves approximation ratio for the localized greedy algorithm (without the in the element weight).

# Questions for later

Generalize to constrained Set Multicover (where the solution must take each set at most once). Aim for -approximation (matching Wolsey).