A greedy algorithm for unconstrained Set Multicover

{\rm H}(n)-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 x
  output: multicover \tilde x
1. Initialize \tilde x_ s = 0 for every set s.
2. Repeat until every element is covered:
3. Sample a set s from the distribution x/|x|.
4. Increase \tilde x_ s by 1.
5. Return \tilde x.
Lemma (existence proof).

Fix a problem instance. Let n be the number of elements. The set cover \tilde x returned by the rounding scheme has expected cost at most {\rm H}(n)\, c\cdot x.

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 \tilde x
1. Initialize \tilde x_ s = 0 for every set s.
2. Repeat until every element is covered:
3. Choose a set s to maximize \displaystyle \sum _{e\in s : \tilde x(e) \lt d_ e} \frac{1}{c_ s d_ e}.
4. Increase \tilde x_ s by 1.
5. Return \tilde x.

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

This performance guarantee follows as a corollary:

Theorem.

The algorithm above returns a multicover of cost at most {\rm H}(n)\, {\textsc{opt}}, where {\textsc{opt}} 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 {\rm H}(\max _ s |s|). The localized greedy algorithm is not the one directly above. It is the same as the algorithm from the reduction (it chooses the set s in each iteration to maximize the number of not-yet-satisfied elements in s divided by c_ s.)

This approach generalizes to unconstrained Multiset Multicover (where each set s covers element e with a given integer multiplicity A_{se}). The localized analysis gives approximation ratio {\rm H}(\max _{s} \sum _ e A_{se}). The same result can be obtained by applying Wolsey’s generalization of the Set-Cover algorithm [1, 3], using the following submodular constraint for x\in {\mathbb N}_+^ m: that \sum _{e} \min \{ d_ e, \sum _{s} A_{es} x_ s\} \ge \sum _ e d_ e. That approach proves approximation ratio {\rm H}(\max _ s \sum _ e A_{se}) for the localized greedy algorithm (without the 1/d_ e in the element weight).

Questions for later

Generalize to constrained Set Multicover (where the solution must take each set s at most once). Aim for {\rm H}(\max _ s |s|)-approximation (matching Wolsey).

MathJax is loading, equations are not yet displayed...