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.

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