Non-uniform increments

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.
Lemma (existence proof).

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

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 any integer \delta _ s \le \min _{e\in s} d_ e – \tilde x(e).
5. Return \tilde x.
Proof sketch.

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

\[ c_{s} ~ \le ~ \frac{c\cdot x}{\lceil n_ t\rceil }\sum _{\tilde x(e)\lt d_ e}\frac{[e\in s]}{d_ e}. \]

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:

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.

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

Choosing the increments to guarantee iteration count.

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.