# 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 , let denote the coverage of , that is, .

Here is a rounding scheme with non-uniform increments:

 input: fractional multicover output: multicover 1. Initialize for every set . 2. Repeat until every element is covered: 3. For each element , let denote its residual demand. 4. For each set , fix an arbitrary integer increment , 5. and define probability (choosing so ). 6. Sample a set from the distribution . 7. Increase by . 8. Return .
Lemma (existence proof).

Fix a problem instance. Let be the number of elements. The multiset cover returned by the rounding scheme has expected cost at most .

# 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 1. Initialize for every set . 2. Repeat until every element is covered: 3. Choose a set to maximize . 4. Increase by any integer . 5. Return .
Proof sketch.

We claim the algorithm keeps the pessimistic estimator (defined in the existence proof) from increasing. Indeed, the algorithm’s choice of 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 , where 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 corresponds to simulating iterations of unit increments — once the unit-increment algorithm chooses a particular set , it will remain a valid choice for at least more iterations).

Choosing the increments to guarantee iteration count.

Finally, if the algorithm chooses each increment 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 .