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.

Click for background material…

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

Click for proof…

For the special case with unit increments (where $\delta _s = 1$ for all sets in every iteration) we showed ${\rm H}(n)$ -approximation in this example. The proof is a trivial generalization of that proof.

Let stopping time $T$ be the number of samples. As the rounding scheme proceeds, after $t$ samples, recall that the fractional number uncovered is

$n_t = \sum _e \max \{ 0, \, 1-\tilde x(e)/d_e\} .$

Recall, from the method of conditional probabilities in the previous proof, that the pessimistic estimator was

$\phi _t ~ =~ c\cdot \tilde x \, +\, \tilde{\rm H}(n_t) \, c\cdot x,$

where $\tilde{\rm H}(y) = \int _{0}^y 1/\lceil z \rceil \, dz$ .

We re-use the same pessimistic estimator here. (But to analyze the rounding scheme!)

Following the inequalities from the previous proof, when a set $s$ is chosen in iteration $t+1$ and $\tilde x_s$ is increased by $\delta _s$ , (letting $\delta$ and $\alpha$ denote their values at the start of iteration $t+1$ ) the increase in the pessimistic estimator satisfies

$\begin{align} \phi _{t+1} - \phi _{t} ~ \le ~ & \delta _s c_{s} \, -\, \frac{n_{t} - n_{t+1}}{\lceil n_t\rceil }\, c\cdot x \notag \\ ~ =~ & \delta _s c_{s} \, -\, \frac{c\cdot x}{\lceil n_t\rceil }\sum _{\tilde x(e)\lt d_e}\frac{[e\in s]\delta _s}{d_e}. \label{bound} \end{align}$

We claim that in expectation, \eqref{bound} is non-positive. Before we prove the claim, note that it implies the lemma, because it implies that by Wald’s the expectation of the final value $\phi _T$ is at most the initial value $\phi _0$ ; and the final value $\phi _T$ equals the cost of $\tilde x$ (because $\tilde h(n_T) = 0$ ), while the initial value $\phi _0$ is ${\rm H}(n)\, c\cdot x$ .

To finish we observe that \eqref{bound} is non-positive in expectation.

The expectation of the first term $\delta _s c_s$ , by calculation, is $\sum _s p_s\, \delta _s\, c_s = \sum _s \alpha \, x_s\, c_s = \alpha \, c \cdot x$ .

For each element $e$ , for random $s$ , the expectation of $[e\in s]\delta _s/d_e$ is $\sum _{s\ni e} p_s \delta _s/d_e = \sum _{s\ni e} \alpha x_s/d_e \ge \alpha$ .

Given $n_t$ , there are a minimum of $\lceil n_t \rceil$ such not-fully-covered elements. Hence the expectation of the sum in \eqref{bound} is at least $\alpha \lceil n_t\rceil$ . The claim follows.

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

Notes on algorithms

Lecture notes on algorithms

Non-uniform increments

The rounding scheme

Applying the method of conditional probabilities