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

A derivation of a GRASP (greedy randomized adaptive search procedure) for -approximating unweighted Set Cover.

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

# Greedy randomized search procedure (GRASP)

To start we summarize the algorithm that we will, in the end, derive. Let be the number of elements to cover. Let be an upper bound on the size of an optimal set cover. (If is unknown, do binary search for it in .)

 input: collection of sets over universe , upper bound output: w/probability , a set cover of size . 1. Let . Let . 2. Create tokens, each with an associated unit-rate Poisson process. 3. As time increases continuously from to : 4. When a Poisson process fires at time , remove its token from its current set (if any), then place it on a set chosen to maximize $\sum _{e\in s} \Big( \frac{1-1/{\textsc{opt}}}{1/f(t) – 1/{\textsc{opt}}} \Big)^{C^{(t)}_ e},$ where denotes the number of tokens (other than the firing token) currently covering element , and . 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 , the weight of element is about , so the algorithm essentially moves tokens onto the largest sets. When , the weight of an element is about . Thus, each token on a set covering cuts ’s weight by a factor of . Finally, when , an element has weight about , so only uncovered (or minimally covered) elements contribute significant weight.

If is unknown, then binary search can be used to find the smallest integer between and for which the algorithm works.

# Analysis

Next we prove the following performance guarantee.

Theorem.

If there exists a fractional set cover of size , then, with probability at least 1/2, the algorithm returns a set cover of size at most .

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

Rounding scheme.

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

Analysis.

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

Lemma.

For and , with probability at least 1/2, the rounding scheme returns a set cover of size at most .

Proof.

Fix a set . The probability that a given token doesn’t fire in time units is . If it does fire, the probability that it ends up on is . Thus, the probability that a given token ends up on is .

Therefore, for any fixed element , the probability that a given token ends up covering (that is, ends up on a set containing ) is .

Since the tokens are independent, the probability that is not covered at the end (i.e., the probability that no token ends up covering ) 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 , let be the probability that a given token will fire in the remaining time units. If a token is currently covering , the conditional probability that it will not cover at the end is at most (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 now, the conditional probability that it will end up not covering is at most .

Let denote the number of tokens currently covering . Since the tokens are independent, the conditional probability that no token will end up covering 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 . This is our pessimistic estimator.

The reader can verify that does not increase in expectation as increases. (It is enough to show that, for small, .)

# 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 chosen to minimize the resulting value of . With this modification, is still non-increasing with in expectation, so a set cover of size 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 to , the pessimistic estimator defined previously is non-increasing in expectation. Thus, . Thus, . Finally, if , then each element is covered.

open problem:

Simplify the algorithm, removing the awkward dependence on .