${\rm H}(n)$ -approximation for unconstrained Set Multicover by oblivious randomized rounding.

This example illustrates the use of “Wald’s equation for dependent decrements”. The rounding scheme and algorithm can be exponentially slow. In a later example, we speed it up using non-uniform increments.

Click for background material…

The rounding scheme

Fix an instance of unconstrained Set Multicover. Here is the rounding scheme:

	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.	Sample a set $s$ from the distribution $x/\|x\|$ .
4.	Increase $\tilde x_ s$ by 1.
5.	Return $\tilde x$ .

Lemma (existence proof).

Fix a problem instance. Let $n$ be the number of elements. The set cover $\tilde x$ returned by the rounding scheme has expected cost at most ${\rm H}(n)\, c\cdot x$ .

Click for proof…

The proof generalizes the proof of the ${\rm H}(n)$ -approximation for weighted Set Cover.

Let $\tilde x(e) = \sum _{s\ni e} \tilde{x_ s}$ denote the extent to which $\tilde x$ covers element $e$ . As the rounding scheme proceeds, after $t$ samples, define the fractional number uncovered to be

\[ n_ t = \sum _ e \max \{ 0, \, 1-\tilde x(e)/d_ e\} . \]

Intuitively, this counts the “number” of elements left to cover, where an element $e$ is counted as fractionally covered when its coverage $\tilde x(e)$ is less than its demand $d_ e$ .

For each element $e$ that is not yet fully covered, the next sample will increase the coverage $\tilde x(e)$ of $e$ by 1 with probability at least $d_ e/|x|$ . (The probability is $\sum _{s\ni e} x_ s/|x| \ge d_ e/|x|$ .) Thus, in expectation, $\tilde x(e)$ will increase by at least $d_ e/|x|$ , so, in expectation, $1-\tilde x(e)/d_ e$ will decrease by at least $1/|x|$ .

Given $n_ t$ , there are a minimum of $\lceil n_ t \rceil$ such not-fully-covered elements. Hence, inspecting the definition of $n_ t$ , the next sample will decrease it by at least $\lceil n_ t \rceil /|x|$ in expectation:

\[ \textrm{E}[n_{t} – n_{t+1} \, |\, n_ t] ~ \ge ~ \lceil n_ t \rceil / |x|. \]

By Wald’s for dependent decrements (being careful to use the ceiling in the inequality above), this implies that the number of samples, $T$ , before all elements are covered has expectation

\[ \textstyle \textrm{E}[T] ~ \le ~ \int _0^{n} |x| / \lceil z \rceil \, dz ~ =~ |x|\, {\rm H}(n). \]

Each of the $T$ sampled sets contributes $\sum _ s (x_ s/|x|) c_ s = c\cdot x/|x|$ in expectation to the final cost of $\tilde x$ . So, by Wald’s equation, the total expected cost is at most $(c\cdot x/|x|) \textrm{E}[T] \le c\cdot x\, {\rm H}(n)$ .

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 1.
5.	Return $\tilde x$ .

This greedy algorithm differs from the one following from the reduction to Set Cover, in that, in choosing $s$ , it gives each element weight $1/d_ e$ instead of $1$ .

Click for proof…

Let random variable $Q$ be the cost of the final cover $\tilde x$ . The algorithm will keep the conditional expectation of $Q$ below ${\rm H}(n)\, c\cdot x$ .

Let $\tilde x$ denote the rounded solution after $t$ samples. Define $n_ t$ to be the fractional number uncovered (elements) as in the existence proof. Reasoning as in the existence proof (and from the proof of Wald’s for dependent decrements),

The expected number $T-t$ of samples needed to fully cover the remaining elements is at most $|x|\tilde{\rm H}(n_ t)$ , where

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

is the piecewise-linear extension of the function ${\rm H}(n)$ to the positive reals.
Each remaining sample costs $c\cdot x/|x|$ in expectation.

Hence, by Wald’s equation, the total expected remaining cost is at most the product $[|x| \tilde{\rm H}(n_ t) ] c\cdot x/|x| = \tilde{\rm H}(n_ t)c\cdot x$ . That is, given $\tilde x$ , the conditional expectation of $Q$ is at most

\[ \phi _ t ~ =~ c\cdot \tilde x \, +\, \tilde{\rm H}(n_ t) \, c\cdot x. \]

The algorithm will keep this pessimistic estimator $\phi _ t$ from increasing in each iteration. When a set $s$ is chosen in iteration $t+1$ , the increase $\phi _{t+1} - \phi _ t$ equals

\[ c_{s} ~ -~ [\tilde{\rm H}(n_{t}) – \tilde{\rm H}(n_{t+1})] c\cdot x. \]

Recalling the key inequality $\tilde{\rm H}(n_{t}) - \tilde{\rm H}(n_{t+1}) \ge (n_ t - n_{t+1})/\lceil n_ t\rceil$ from Wald’s for dependent decrements, this increase is at most

\begin{equation} \label{desired} c_{s} \, -\, \frac{n_{t} – n_{t+1}}{\lceil n_ t\rceil }\, c\cdot x. \end{equation}

For a set $s$ chosen randomly from $x/|x|$ , the bound \eqref{desired} is non-positive in expectation, because $\textrm{E}[c_{s}] = c\cdot x/|x|$ while $\textrm{E}[n_ t - n_{t+1}] \ge \lceil n_ t\rceil /|x|$ .

Therefore, there exists a set $s$ for which the bound is non-positive. Gathering terms that depend on $s$ (namely $c_{s}$ and $n_ t-n_{t+1}$ ), the bound is non-positive iff

\[ (n_ t – n_{t+1})/c_{s} \, \ge \, \lceil n_ t\rceil \, c\cdot x. \]

Since some set $s$ satisfies this, the set $s$ that maximizes the left-hand side satisfies it. This is the set that the greedy algorithm chooses. Thus, the greedy algorithm is guaranteed to reach a successful outcome.

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.

Localizing gives ${\rm H}(\max _ s|s|)$ -approximation

We note without recording the proof that localizing the above rounding scheme improves the approximation ratio of the rounding scheme and algorithm to ${\rm H}(\max _ s |s|)$ . The localized greedy algorithm is not the one directly above. It is the same as the algorithm from the reduction (it chooses the set $s$ in each iteration to maximize the number of not-yet-satisfied elements in $s$ divided by $c_ s$ .)

This approach generalizes to unconstrained Multiset Multicover (where each set $s$ covers element $e$ with a given integer multiplicity $A_{se}$ ). The localized analysis gives approximation ratio ${\rm H}(\max _{s} \sum _ e A_{se})$ . The same result can be obtained by applying Wolsey’s generalization of the Set-Cover algorithm , using the following submodular constraint for $x\in {\mathbb N}_+^ m$ : that $\sum _{e} \min \{ d_ e, \sum _{s} A_{es} x_ s\} \ge \sum _ e d_ e$ . That approach proves approximation ratio ${\rm H}(\max _ s \sum _ e A_{se})$ for the localized greedy algorithm (without the $1/d_ e$ in the element weight).

Questions for later

Generalize to constrained Set Multicover (where the solution must take each set $s$ at most once). Aim for ${\rm H}(\max _ s |s|)$ -approximation (matching Wolsey).

Bibliography

[1]	G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, New York, 1988.
[2]	V. Vazirani. Approximation Algorithms. Springer Verlag, 2003.
[3]	L. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393, 1982.

Notes on algorithms

Lecture notes on algorithms

A greedy algorithm for unconstrained Set Multicover

The rounding scheme

Applying the method of conditional probabilities

Localizing gives ${\rm H}(\max _ s|s|)$ -approximation

Questions for later

Related

Bibliography

The rounding scheme

Applying the method of conditional probabilities

Localizing gives {\rm H}(\max _ s|s|){\rm H}(\max _ s|s|)-approximation

Questions for later

Related

Bibliography

Localizing gives ${\rm H}(\max _ s|s|)$ -approximation