This introductory example illustrates the basic idea. The rounding scheme randomly samples a fixed number $N = \lceil |x|\ln n\rceil$N = \lceil |x|\ln n\rceil of sets from the distribution defined by the fractional solution $x$x. By direct calculation, the expected number of elements left uncovered is less than 1. Applying the method of conditional probabilities yields Johnson and Lovász’s greedy set-cover algorithm, and a proof that it returns a cover of size at most $\lceil |x^*|\ln n\rceil$\lceil |x^*|\ln n\rceil , where $x^*$x^* is an optimal fractional cover. More on deriving the greedy set-cover algorithm…

For problems whose cost functions have weights, the increase in cost with each sample depends on the sample. Also, instead of sampling for a pre-determined number of samples, the most natural rounding scheme stops when some condition is met (such as when all elements are covered). The analysis of the rounding scheme becomes a little more subtle. The analysis for the unweighted case can be adapted by using Wald’s equation.

In this example, the rounding scheme samples from the distribution defined by the fractional solution until all elements are covered. We use Wald’s equation to show that the expected number of samples before all elements are covered is at most $|x|{\rm H}(n)$|x|{\rm H}(n), so the expected cost of all the samples is at most $c\cdot x\, {\rm H}(n)$c\cdot x\, {\rm H}(n) (the fractional cost times ${\rm H}(n)=1+1/2+\cdots +1/n${\rm H}(n)=1+1/2+\cdots +1/n). Applying the method of conditional probabilities yields Chvátal’s algorithm (which generalizes the greedy set-cover algorithm to the weighted case), and a proof that it returns a ${\rm H}(n)${\rm H}(n)-approximation. More on using Wald’s to handle weighted set cover…

Here $d = \max _ s |s|$d = \max _ s |s| is the maximum set size. The analyses in the examples above analyze the number of samples necessary to meet all $n$n constraints, then multiply that by the cost per sample. With this “global” approach, the approximation ratio inevitably grows as $n$n increases, because the number of samples required to meet all constraints grows with $n$n (it’s about $|x|{\rm H}(n)$|x|{\rm H}(n)). We can avoid this by recasting the analysis to make it “local”.

In this example, we modify the random sampling scheme so that, when a set $s$s is sampled, the set is added to the cover only if $s$s contains an element that is not yet covered. For the analysis we focus on each set $s$s in isolation. Following the same reasoning as in the global analysis, the expected number of samples before all elements in $s$s are covered is at most $|x|{\rm H}(|s|)$|x|{\rm H}(|s|). (And $s$s won’t be added to the cover after that.) Thus, the probability that $s$s is added is at most $x_ s{\rm H}(|s|)$x_ s{\rm H}(|s|). By linearity of expectation the expected cost of the final cover is at most $\sum _ s c_ s x_ s {\rm H}(|s|)$\sum _ s c_ s x_ s {\rm H}(|s|).

Applying the method of conditional probabilities yields Chvátal’s algorithm again (although the pessimistic estimator is more subtle) and a proof that the algorithm returns a cover of cost at most $\min _{x^*} \sum _ s c_ s x^*_ s {\rm H}(|s|)$\min _{x^*} \sum _ s c_ s x^*_ s {\rm H}(|s|), which is at most ${\rm H}(d)\min _{x^*} c\cdot x^*${\rm H}(d)\min _{x^*} c\cdot x^*, where $x^*$x^* ranges over the feasible fractional set covers.

More on improving the bound by localizing it…