Trivial example: Vertex Cover

Here is a very simple randomized-rounding scheme for Vertex Cover:

1. Given any graph $G$G, compute a min-cost fractional vertex cover $x^*$x^*.
2. Return the random vertex cover $\tilde x$\tilde x where $\tilde x_ v = 1$\tilde x_ v = 1 with probability $\min (2x^*_ v,1)$\min (2x^*_ v,1).

The algorithm is a 2-approximation algorithm in expectation. Indeed, the rounded solution $\tilde x$\tilde x is a cover because for any edge one of its two endpoints $v$v must have $x^*_ v \ge 1/2$x^*_ v \ge 1/2, which forces $v$v into the cover $\tilde x$\tilde x. By inspection, the expected cost of $\tilde x$\tilde x is at most twice the cost of $x^*$x^*, which, since the cost of $x^*$x^* is a lower bound on the cost of the integral opt, is at most $2{\textsc{opt}}$2{\textsc{opt}}.

Relation to the probabilistic method in combinatorics

If you’re already familiar with the probabilistic method, the new element here is that the fractional solution $x^*$x^* is used as basis for the probability distribution. This allows the cost of the rounded solution to be related to the cost of $x^*$x^*, and via that (since $x^*$x^* is an optimal solution to a relaxation) to the cost of opt. In this way, one obtains the per-input worst-case performance guarantees necessary for approximation algorithms.

Standard randomized-rounding scheme for Set Cover

Next is a more sophisticated example of randomized rounding: a standard randomized-rounding scheme for Set Cover. This example is comparable to one in [4, Sec.14.2]. For more examples, see [1, ch.4].

(Note: with care the $O(\log n)$O(\log n) can be reduced to $\ln (n)+O(\log \log n)$\ln (n)+O(\log \log n).)

Deconstructing the Set Cover existence proof to find $Q$Q

The argument above shows the existence of a set cover of cost $O(\log (n)c\cdot x^*$O(\log (n)c\cdot x^*). The next step is to apply the method of conditional probabilities to the existence proof. The resulting algorithm will consider each set $s\in S$s\in S in turn, and set $\tilde x_ s$\tilde x_ s to either 0 or 1. Instead of setting $\tilde x_ s$\tilde x_ s randomly based on $x^*$x^*, it will set $\tilde x_ s$\tilde x_ s to keep the conditional probability of failure (defined with respect to the random experiment) below 1.

Although the concept is simple, implementing it requires a careful calculation bounding the conditional probability of failure as the scheme proceeds. The original existence proof implicitly bounds the (unconditioned) probability of failure by the expectation of

where $n_ m$n_ m is the number of elements left uncovered at the end that is, $n_ m$n_ m is the size of the set $U_ m=\{ e\, \, |\, \, \forall s\ni e.~ \tilde x_ s = 0 \}$ U_ m=\{ e\, \, |\, \, \forall s\ni e.~ \tilde x_ s = 0 \} .

The form of $Q$Q mirrors the probabilistic proof in a systematic way.¹ The first term in $Q$Q comes from applying the Markov bound to bound the probability of the first bad event. It contributes at least 1 to $Q$Q if the cost is too high. The second term $n_ m$n_ m counts the number of bad events of the second kind (uncovered elements). It contributes at least 1 to $Q$Q if the coverage fails. Since failure implies $Q\ge 1$Q\ge 1, by the Markov bound, the probability of failure is at most $E[Q]$E[Q]. Finally (as shown by calculation in the proof of the lemma) $E[Q] \lt 1$E[Q] \lt 1.

Algorithm via the method of conditional probabilities

The algorithm will choose each set to keep the conditional expectation of $Q$Q, given the choices made so far, below 1. Consider the state after the $t$tth choice. Let $S_ t=(s_1,s_2,\ldots ,s_ t)$S_ t=(s_1,s_2,\ldots ,s_ t) denote the sets considered so far — for each set $s\in S_ t$s\in S_ t, the value of $\tilde x_ s$\tilde x_ s has been set to 0 or 1; the values for the remaining sets have not yet been determined. The conditional expectation of $Q$Q, given this state, is

The algorithm will keep $\phi _ t$\phi _ t (the conditional expectation of $Q$Q) below 1 by setting each $\tilde x_{s_ t}$\tilde x_{s_ t} to minimize the resulting value of $\phi _ t$\phi _ t. Let $s’=s_ t$s’=s_ t denote the $t$tth set. When the algorithm sets $\tilde x_{s'}$\tilde x_{s’}, each $\tilde x_ s$\tilde x_ s for $s\in S_{t-1}$s\in S_{t-1} has already been set. Considered as a function of just $\tilde x_{s'}$\tilde x_{s’} (with all other quantities fixed) the quantity $\phi _ t$\phi _ t is linear in $\tilde x_{s'}$\tilde x_{s’}. Let $U= \{ e \, |\, \prod _{s\in S_{t-1}} (1-[e\in s] \tilde x_ s) = 1\}$U= \{ e \, |\, \prod _{s\in S_{t-1}} (1-[e\in s] \tilde x_ s) = 1\} denote the set of elements not covered before $s’$s’ is considered. The coefficient of $\tilde x_{s'}$\tilde x_{s’} in $\phi _ t$\phi _ t is

To minimize $\phi _ t$\phi _ t, if this coefficient is positive, then the algorithm sets $\tilde x_{s'}$\tilde x_{s’} to 0. Otherwise it sets $\tilde x_{s'}$\tilde x_{s’} to 1:

By ensuring $\phi _ t \le \phi _{t-1}$\phi _ t \le \phi _{t-1} at each step, the algorithm guarantees an outcome with $Q\le \textrm{E}[Q]\lt 1$Q\le \textrm{E}[Q]\lt 1, so that $\tilde x$\tilde x has cost at most $2\ln (2n)c\cdot x^*$2\ln (2n)c\cdot x^* and covers all elements:

Randomized rounding without solving the linear program

The algorithm’s choice for each $\tilde x_{s'}$\tilde x_{s’} depends intrinsically on the individual values within $x^*$x^*. (For example, if each element $e\in s’$e\in s’ is contained in some not-yet-considered set $s$s with $p_{s}=1$p_{s}=1, then $s’$s’ will not be added to the cover even if $p_{s'}=1$p_{s’}=1.) This dependence is not surprising, but it is not inevitable. By starting with a different randomized rounding scheme, the method of conditional probabilities can yield an algorithm that, in each step, makes a choice that is the same for any feasible $x^*$x^*. Thus, the algorithm can compute the approximate cover $\tilde x$\tilde x without first computing $x^*$x^*. You can read more about that here.