# Greedy Set Cover I: unweighted ln(n)-approximation

Randomized rounding yields the Johnson/Lovász greedy algorithm for unweighted Set Cover.

The rounding scheme samples sets i.i.d. from the fractional cover until all elements are covered. Applying the method of conditional probabilities yields the Johnson/Lovász greedy algorithm for unweighted Set Cover, and a proof that it is a -approximation algorithm.

# Randomized-rounding scheme for unweighted Set Cover

 input: Set-Cover instance output: set cover for 0. Compute a fractional set cover minimizing . 1. Repeat until the sampled sets form a cover: 2. Sample a random set from the distribution defined by . 3. Return the sampled sets.

Note: denotes the 1-norm of .

Lemma (existence, ).

Let be the number of elements. With non-zero probability the rounding scheme returns a set cover of size at most .

Proof.

The fractional solution gives total weight at least 1 to the sets containing any given element , so the probability that is covered in any given round is at least . Hence, after rounds, the expected number of the elements left uncovered is at most which is strictly less than , which is 1 or less by the choice of .

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

Lemma (algorithm, ).

Applying the method of conditional probabilities to the existence proof yields the following algorithm.

# Greedy algorithm for Set Cover (unweighted): ln(n)-approximation

 input: Set-Cover instance output: set cover for 1. Repeat until the chosen sets form a cover: 2. Choose a set that contains a maximum number of elements that are not yet covered by chosen sets. 3. Return the chosen sets.

To derive the algorithm, we need an appropriate pessimistic estimator for the expectation of the number of elements that will be left uncovered by the end of iteration , conditioned on the state at the end of a given iteration . Letting denote the number of elements remaining uncovered at the end of iteration , this conditional expectation is at most

\begin{eqnarray} \label{eq} \phi _ t ~ =~ n_ t(1-1/|x^*|)^{T-t}. \end{eqnarray}

The algorithm chooses the set that contains a maximum number of not-yet-covered elements. This choice also minimizes the resulting value of the pessimistic estimator. (The factor of in can be ignored, since it is independent of the choices made by the algorithm. Hence, minimizing is the same as minimizing .) Hence, the algorithm guarantees a successful outcome.

Theorem ([1, 2]).

For unweighted set cover with , the greedy Set-Cover algorithm returns a cover of size at most , where is the minimum size of any fractional cover and is the number of elements.