${\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|)-approximation

Questions for later

Related

Bibliography

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