# Set Cover / alterations

Yet another approximation ratio for Chvátal’s greedy set-cover algorithm.

We show that the rounding scheme and algorithm give -approximate solutions, matching bounds of Srinivasan [2, Thm.5.2(b)] and Slavik [1]. For unweighted set cover, this bound compares favorably to the -approximation ratio, because is always at most (the maximum set size). For the weighted case the bounds are incomparable. The proof is related to the so-called method of alterations.

# The algorithm

We prove the following theorem by applying the method of conditional probabilities to the localized rounding scheme:

Theorem [1]).

Assuming the cost of each set is at most , Chvátal’s algorithm returns a cover of cost at most .

To prove the theorem, we first analyze the rounding scheme:

Lemma.

Assume the cost of each set is at most . With non-zero probability, the cost of the random set cover is less than .

Proof of lemma.

Define (with foresight) . Let denote the number of elements remaining after samples. Let stopping time be the number of samples until the cumulative cost of sampled sets is in the range , so that the total cost of the sets chosen in this first stage is less than . In the second stage, elements are initially not-yet-covered, and then each set chosen covers at least 1 new element and costs at most 1. So the total cost of the second stage is at most . Thus, the total cost of all sets chosen is less than . To finish the proof, we show that with positive probability is at most , in which case the upper bound on the total cost is at most , as desired.

# Method of conditional probabilities

To prove the theorem, we show that applying the method of conditional probabilities to the lemma yields the algorithm.

Proof of theorem.

Define , , and as in the proof of the lemma. Following the proof of the lemma, in any outcome where is less than , the performance guarantee holds. We show that the algorithm chooses each of the first sets to keep the conditional expectation of below . It does so by keeping the following pessimistic estimator from decreasing:

$\phi _ t ~ =~ \ln (n_ t) \, – \, \frac{\alpha -C_ t}{c\cdot x},$

where (abusing notation) denotes the cost of the first sampled sets.