A derivation of a GRASP (greedy randomized adaptive search procedure) for $O(\log n)$ -approximating unweighted Set Cover.

In this example we only partially derandomize the rounding scheme. The final algorithm still makes some choices randomly.

Click for background material…

Deriving greedy algorithms via randomized rounding.

Greedy randomized search procedure (GRASP)

To start we summarize the algorithm that we will, in the end, derive. Let $n=|\cal U|$ be the number of elements to cover. Let ${\textsc{opt}}= |x^*|$ be an upper bound on the size of an optimal set cover. (If ${\textsc{opt}}$ is unknown, do binary search for it in $\{ 1,2,\ldots ,n\}$ .)

	input: collection ${\cal S}$ of sets over universe ${\cal U}$ , upper bound ${\textsc{opt}}$
	output: w/probability $\ge 1/2$ , a set cover ${\cal C}$ of size $O({\textsc{opt}}\ln n)$ .
1.	Let $K=\lceil \ln (2n){\textsc{opt}}/0.99\rceil$ . Let $T=\ln (100)$ .
2.	Create $K$ tokens, each with an associated unit-rate Poisson process.
3.	As time $t$ increases continuously from $0$ to $T$ :
4.	When a Poisson process fires at time $t$ , remove its token from its current set (if any), then place it on a set $s$ chosen to maximize $\sum _{e\in s} \Big( \frac{1-1/{\textsc{opt}}}{1/f(t) - 1/{\textsc{opt}}} \Big)^{C^{(t)}_e},$ where $C^{(t)}_e$ denotes the number of tokens (other than the firing token) currently covering element $e$ , and $f(t) \doteq 1-\exp (-(T-t))$ .
5.	Return the sets that have tokens on them.

When a token fires, it moves to a set whose elements have largest total “weight”. Initially, when $t\approx 0$ , the weight of element $e$ is about $.99^{C_e} \approx 1$ , so the algorithm essentially moves tokens onto the largest sets. When $t\approx T-\ln 2$ , the weight of an element $e$ is about $.5^{C_e}$ . Thus, each token on a set covering $e$ cuts $e$ ’s weight by a factor of $1/2$ . Finally, when $t\approx T-\varepsilon$ , an element $e$ has weight about $\varepsilon ^{C_e}$ , so only uncovered (or minimally covered) elements contribute significant weight.

If ${\textsc{opt}}$ is unknown, then binary search can be used to find the smallest integer ${\textsc{opt}}$ between $1$ and $n$ for which the algorithm works.

Analysis

Next we prove the following performance guarantee.

Theorem.

If there exists a fractional set cover $x^*$ of size ${\textsc{opt}}$ , then, with probability at least 1/2, the algorithm returns a set cover of size at most $\lceil \ln (2n){\textsc{opt}}/0.99\rceil$ .

We prove the theorem by deriving the algorithm from the following randomized-rounding scheme.

Rounding scheme.

Given any fractional solution $x^*$ over $n$ elements, randomly round it to an integer solution (a collection of sets) as follows. Use $K$ tokens. For each token in parallel, run a Poisson process of unit intensity for $T$ time units. When the Poisson process for a token fires, choose a set from probability distribution $x^*/{\textsc{opt}}$ and move the token onto the set. After $T$ time units, return the sets that have tokens.

Analysis.

The rounding scheme clearly produces at most $K$ sets. These sets are likely to form a cover for reasonably small $K$ and $T$ :

Lemma.

For $K\ge \ln (2n){\textsc{opt}}/0.99$ and $T=\ln 100$ , with probability at least 1/2, the rounding scheme returns a set cover of size at most $K$ .

Proof.

Fix a set $s$ . The probability that a given token doesn’t fire in $T$ time units is $\exp (-T) = 0.01$ . If it does fire, the probability that it ends up on $s$ is $x^*_s/{\textsc{opt}}$ . Thus, the probability that a given token ends up on $s$ is $0.99 x^*_s/{\textsc{opt}}$ .

Therefore, for any fixed element $e$ , the probability that a given token ends up covering $e$ (that is, ends up on a set containing $e$ ) is $\sum _{s\ni e}0.99\, x^*_s/{\textsc{opt}}\ge 0.99/{\textsc{opt}}$ .

Since the tokens are independent, the probability that $e$ is not covered at the end (i.e., the probability that no token ends up covering $e$ ) is at most

$\renewcommand{\mathspread }{\, \, \, }(1 - 0.99/{\textsc{opt}})^K {\, \, \, {<}\, \, \, }\exp (- 0.99 K/{\textsc{opt}}) {\, \, \, {\le }\, \, \, }1/(2n).$

By the naive union bound, the probability that there exists an uncovered element is less than 1/2.

Pessimistic estimator

Next we apply the method of conditional probabilities to derive the algorithm.

At time $t$ , let $f(t) \doteq 1-\exp (-(T-t))$ be the probability that a given token will fire in the remaining $T-t$ time units. If a token is currently covering $e$ , the conditional probability that it will not cover $e$ at the end is at most $\renewcommand{\mathspread }{\, \, \, }f(t)( 1- 1 / {\textsc{opt}}),$ (the probability that the token will fire times an upper bound on the probability it will end up elsewhere if it does). Likewise, if a token is not covering $e$ now, the conditional probability that it will end up not covering $e$ is at most $1 - f(t)/{\textsc{opt}}$ .

Let ${C}^{\scriptscriptstyle (t)}_e$ denote the number of tokens currently covering $e$ . Since the tokens are independent, the conditional probability that no token will end up covering $e$ is at most

$\renewcommand{\mathspread }{\, \, \, }\psi _{et} {\, \, \, {\doteq }\, \, \, }\big(f(t) - f(t) / {\textsc{opt}}\big)^{\textstyle {C}^{\scriptscriptstyle (t)}_e} \times \big(1 - f(t) / {\textsc{opt}}\big)^{\textstyle K - {C}^{\scriptscriptstyle (t)}_e} .$

By the naive union bound, the conditional probability that there will be a not-covered element is at most $\Phi _t \doteq \sum _e \psi _{et}$ . This is our pessimistic estimator.

The reader can verify that $\Phi _t$ does not increase in expectation as $t$ increases. (It is enough to show that, for $\varepsilon$ small, $\renewcommand{\mathspread }{\, \, \, }\textrm{E}[\Phi _{t+\varepsilon } - \Phi _t \, |\, \Phi _t] {\, \, \, {\le }\, \, \, }o(\varepsilon )$ .)

Algorithm

To obtain the algorithm, derandomize only the random choices of sets. Namely, let the tokens fire randomly, but when a token fires, move the token to a set $s$ chosen to minimize the resulting value of $\Phi _t$ . With this modification, $\Phi _t$ is still non-increasing with $t$ in expectation, so a set cover of size $K$ will still be found with probability at least 1/2. This gives the algorithm.

Here is the proof of the approximation guarantee:

Proof.

As time proceeds from $t=0$ to $t=T$ , the pessimistic estimator $\Phi _t$ defined previously is non-increasing in expectation. Thus, $\textrm{E}[\Phi _T] \le \Phi _0 \le 1/2$ . Thus, $\Pr [\Phi _T \ge 1] \, \le \, 1/2$ . Finally, if $\Phi _T \lt 1$ , then each element is covered.

open problem:

Simplify the algorithm, removing the awkward dependence on ${\textsc{opt}}$ .

Notes on algorithms

Lecture notes on algorithms

Set Cover / GRASP (greedy randomized search procedure; unweighted)

Greedy randomized search procedure (GRASP)

Analysis

Pessimistic estimator

Algorithm

Related