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