Applying non-uniform increments to unconstrained Set Multicover.
The algorithm in the previous note can be exponentially slow. Here we use non-uniform increments to give a faster rounding scheme and algorithm.
The rounding scheme
For any multicover vector \tilde x, let \tilde x(e) denote the coverage of e, that is, \sum _{s\ni e} \tilde{x_ s}.
Here is a rounding scheme with non-uniform increments:
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. | For each element e, let \tilde d_ e = \max \{ 0, d_ e – \tilde x(e)\} denote its residual demand. |
4. | For each set s, fix an arbitrary integer increment \delta _ s\in [1, \min _{e\in s} d_ e], |
5. | and define probability p_ j \, =\, \alpha \, x_ j/\delta _ j (choosing \alpha so |p| = 1). |
6. | Sample a set s from the distribution p. |
7. | Increase \tilde x_ s by \delta _ s. |
8. | Return \tilde x. |
Fix a problem instance. Let n be the number of elements. The multiset 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 any integer \delta _ s \le \min _{e\in s} d_ e – \tilde x(e). |
5. | Return \tilde x. |
We claim the algorithm keeps the pessimistic estimator \phi _ t (defined in the existence proof) from increasing. Indeed, the algorithm’s choice of s is the same as in the algorithm with unit increments, and, which, as shown in that derivation, ensures that
By inspection, this inequality is equivalent to the upper bound \eqref{bound} on the increase in the pessimistic estimator (from the existence proof) being non-positive.
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.
In hindsight, this theorem has a more direct proof: by inspection, the algorithm above is a direct simulation of the algorithm for unit increments (choosing \delta _ s \gt 1 corresponds to simulating \delta _ s iterations of unit increments — once the unit-increment algorithm chooses a particular set s, it will remain a valid choice for at least \delta _ s more iterations).
Finally, if the algorithm chooses each increment \delta _ s maximally, then each sample (or iteration) will satisfy the demand of at least one element, so the number of samples (or iterations) will be at most the number of elements n.