Randomized rounding

Here is a description of the third step—the rounding step, which must convert the minimum-cost fractional set cover ${\displaystyle x^{*}}$ into a feasible integer solution ${\displaystyle x'}$ (corresponding to a true set cover).

The rounding step should produce an ${\displaystyle x'}$ that, with positive probability, has cost within a small factor of the cost of ${\displaystyle x^{*}}$. Then (since the cost of ${\displaystyle x^{*}}$ is a lower bound on the cost of the optimal set cover), the cost of ${\displaystyle x'}$ will be within a small factor of the optimal cost.

As a starting point, consider the most natural rounding scheme:

For each set ${\displaystyle s\in {\mathcal {S}}}$ in turn, take ${\displaystyle x'_{s}=1}$ with probability ${\displaystyle \min(1,x_{s}^{*})}$, otherwise take ${\displaystyle x'_{s}=0}$.

With this rounding scheme, the expected cost of the chosen sets is at most ${\displaystyle \sum _{s}c(s)x_{s}^{*}}$, the cost of the fractional cover. This is good. Unfortunately the coverage is not good. When the variables ${\displaystyle x_{s}^{*}}$ are small, the probability that an element ${\displaystyle e}$ is not covered is about

${\displaystyle \prod _{s\ni e}1-x_{s}^{*}\approx \prod _{s\ni e}\exp(-x_{s}^{*})=\exp {\Big (}-\sum _{s\ni e}x_{s}^{*}{\Big )}\approx \exp(-1).}$

So only a constant fraction of the elements will be covered in expectation.

To make ${\displaystyle x'}$ cover every element with high probability, the standard rounding scheme first scales up the rounding probabilities by an appropriate factor ${\displaystyle \lambda >1}$. Here is the standard rounding scheme:

Fix a parameter ${\displaystyle \lambda \geq 1}$. For each set ${\displaystyle s\in {\mathcal {S}}}$ in turn,

take ${\displaystyle x'_{s}=1}$ with probability ${\displaystyle \min(\lambda x_{s}^{*},1)}$, otherwise take ${\displaystyle x'_{s}=0}$.

Scaling the probabilities up by ${\displaystyle \lambda }$ increases the expected cost by ${\displaystyle \lambda }$, but makes coverage of all elements likely. The idea is to choose ${\displaystyle \lambda }$ as small as possible so that all elements are provably covered with non-zero probability. Here is a detailed analysis.

Fix ${\displaystyle \lambda =\ln(2|{\mathcal {U}}|)}$. With positive probability, the rounding scheme returns a set cover ${\displaystyle x'}$ of cost at most ${\displaystyle 2\ln(2|{\mathcal {U}}|)c\cdot x^{*}}$ (and thus of cost ${\displaystyle O(\log |{\mathcal {U}}|)}$ times the cost of the optimal set cover).

(Note: with care the ${\displaystyle O(\log |{\mathcal {U}}|)}$ can be reduced to ${\displaystyle \ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)}$.)

The output ${\displaystyle x'}$ of the random rounding scheme has the desired properties as long as none of the following "bad" events occur:

1. the cost ${\displaystyle c\cdot x'}$ of ${\displaystyle x'}$ exceeds ${\displaystyle 2\lambda c\cdot x^{*}}$, or
2. for some element ${\displaystyle e}$, ${\displaystyle x'}$ fails to cover ${\displaystyle e}$.

The expectation of each ${\displaystyle x'_{s}}$ is at most ${\displaystyle \lambda x_{s}^{*}}$. By linearity of expectation, the expectation of ${\displaystyle c\cdot x'}$ is at most ${\displaystyle \sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}}$. Thus, by Markov's inequality, the probability of the first bad event above is at most ${\displaystyle 1/2}$.

For the remaining bad events (one for each element ${\displaystyle e}$), note that, since ${\displaystyle \sum _{s\ni e}x_{s}^{*}\geq 1}$ for any given element ${\displaystyle e}$, the probability that ${\displaystyle e}$ is not covered is

${\displaystyle {\begin{aligned}\prod _{s\ni e}{\big (}1-\min(\lambda x_{s}^{*},1){\big )}&<\prod _{s\ni e}\exp({-}\lambda x_{s}^{*})=\exp {\Big (}{-}\lambda \sum _{s\ni e}x_{s}^{*}{\Big )}\\&\leq \exp({-}\lambda )=1/(2|{\mathcal {U}}|).\end{aligned}}}$

(This uses the inequality ${\displaystyle 1+z\leq e^{z}}$, which is strict for ${\displaystyle z\neq 0}$.)

Thus, for each of the ${\displaystyle |{\mathcal {U}}|}$ elements, the probability that the element is not covered is less than ${\displaystyle 1/(2{\mathcal {U}})}$.

By the naive union bound, the probability that one of the ${\displaystyle 1+|{\mathcal {U}}|}$ bad events happens is less than ${\displaystyle 1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1}$. Thus, with positive probability there are no bad events and ${\displaystyle x'}$ is a set cover of cost at most ${\displaystyle 2\lambda c\cdot x^{*}}$. QED

The lemma above shows the existence of a set cover of cost ${\displaystyle O(\log(|{\mathcal {U}}|)c\cdot x^{*}}$). In this context our goal is an efficient approximation algorithm, not just an existence proof, so we are not done.

One approach would be to increase ${\displaystyle \lambda }$ a little bit, then show that the probability of success is at least, say, 1/4. With this modification, repeating the random rounding step a few times is enough to ensure a successful outcome with high probability.

That approach weakens the approximation ratio. We next describe a different approach that yields a deterministic algorithm that is guaranteed to match the approximation ratio of the existence proof above. The approach is called the method of conditional probabilities.

The deterministic algorithm emulates the randomized rounding scheme: it considers each set ${\displaystyle s\in {\mathcal {S}}}$ in turn, and chooses ${\displaystyle x'_{s}\in \{0,1\}}$. But instead of making each choice randomly based on ${\displaystyle x^{*}}$, it makes the choice deterministically, so as to keep the conditional probability of failure, given the choices so far, below 1.

We want to be able to set each variable ${\displaystyle x'_{s}}$ in turn so as to keep the conditional probability of failure below 1. To do this, we need a good bound on the conditional probability of failure. The bound will come by refining the original existence proof. That proof implicitly bounds the probability of failure by the expectation of the random variable

${\displaystyle F={\frac {c\cdot x'}{2\lambda c\cdot x^{*}}}+|{\mathcal {U}}^{(m)}|}$,

where

${\displaystyle {\mathcal {U}}^{(m)}={\Big \{}e:\prod _{s\ni e}(1-x'_{s})=1{\Big \}}}$

is the set of elements left uncovered at the end.

The random variable ${\displaystyle F}$ may appear a bit mysterious, but it mirrors the probabilistic proof in a systematic way. The first term in ${\displaystyle F}$ comes from applying Markov's inequality to bound the probability of the first bad event (the cost is too high). It contributes at least 1 to ${\displaystyle F}$ if the cost of ${\displaystyle x'}$ is too high. The second term counts the number of bad events of the second kind (uncovered elements). It contributes at least 1 to ${\displaystyle F}$ if ${\displaystyle x'}$ leaves any element uncovered. Thus, in any outcome where ${\displaystyle F}$ is less than 1, ${\displaystyle x'}$ must cover all the elements and have cost meeting the desired bound from the lemma. In short, if the rounding step fails, then ${\displaystyle F\geq 1}$. This implies (by Markov's inequality) that ${\displaystyle E[F]}$ is an upper bound on the probability of failure. Note that the argument above is implicit already in the proof of the lemma, which also shows by calculation that ${\displaystyle E[F]<1}$.

To apply the method of conditional probabilities, we need to extend the argument to bound the conditional probability of failure as the rounding step proceeds. Usually, this can be done in a systematic way, although it can be technically tedious.

So, what about the conditional probability of failure as the rounding step iterates through the sets? Since ${\displaystyle F\geq 1}$ in any outcome where the rounding step fails, by Markov's inequality, the conditional probability of failure is at most the conditional expectation of ${\displaystyle F}$.

Next we calculate the conditional expectation of ${\displaystyle F}$, much as we calculated the unconditioned expectation of ${\displaystyle F}$ in the original proof. Consider the state of the rounding process at the end of some iteration ${\displaystyle t}$. Let ${\displaystyle S^{(t)}}$ denote the sets considered so far (the first ${\displaystyle t}$ sets in ${\displaystyle {\mathcal {S}}}$). Let ${\displaystyle x^{(t)}}$ denote the (partially assigned) vector ${\displaystyle x'}$ (so ${\displaystyle x_{s}^{(t)}}$ is determined only if ${\displaystyle s\in S^{(t)}}$). For each set ${\displaystyle s\not \in S^{(t)}}$, let ${\displaystyle p_{s}=\min(\lambda x_{s}^{*},1)}$ denote the probability with which ${\displaystyle x'_{s}}$ will be set to 1. Let ${\displaystyle {\mathcal {U}}^{(t)}}$ contain the not-yet-covered elements. Then the conditional expectation of ${\displaystyle F}$, given the choices made so far, that is, given ${\displaystyle x^{(t)}}$, is

${\displaystyle E[F|x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)}}c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}$

Note that ${\displaystyle E[F|x^{(t)}]}$ is determined only after iteration ${\displaystyle t}$.

To keep the conditional probability of failure below 1, it suffices to keep the conditional expectation of ${\displaystyle F}$ below 1. To do this, it suffices to keep the conditional expectation of ${\displaystyle F}$ from increasing. This is what the algorithm will do. It will set ${\displaystyle x'_{s}}$ in each iteration to ensure that

${\displaystyle E[F|x^{(m)}]\leq E[F|x^{(m-1)}]\leq \cdots \leq E[F|x^{(1)}]\leq E[F|x^{(0)}]<1}$

(where ${\displaystyle m=|{\mathcal {S}}|}$).

In the ${\displaystyle t}$th iteration, how can the algorithm set ${\displaystyle x'_{s'}}$ to ensure that ${\displaystyle E[F|x^{(t)}]\leq E[F|S^{(t-1)}]}$? It turns out that it can simply set ${\displaystyle x'_{s'}}$ so as to minimize the resulting value of ${\displaystyle E[F|x^{(t)}]}$.

To see why, focus on the point in time when iteration ${\displaystyle t}$ starts. At that time, ${\displaystyle E[F|x^{(t-1)}]}$ is determined, but ${\displaystyle E[F|x^{(t)}]}$ is not yet determined --- it can take two possible values depending on how ${\displaystyle x'_{s'}}$ is set in iteration ${\displaystyle t}$. Let ${\displaystyle E^{(t-1)}}$ denote the value of ${\displaystyle E[F|x'^{(t-1)}]}$. Let ${\displaystyle E_{0}^{(t)}}$ and ${\displaystyle E_{1}^{(t)}}$, denote the two possible values of ${\displaystyle E[F|x^{(t)}]}$, depending on whether ${\displaystyle x'_{s'}}$ is set to 0, or 1, respectively. By the definition of conditional expectation,

${\displaystyle E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{(t)}+\Pr[x'_{s'}=1]E_{1}^{(t)}.}$

Since a weighted average of two quantities is always at least the minimum of those two quantities, it follows that

${\displaystyle E^{(t-1)}~\geq ~\min(E_{0}^{(t)},E_{1}^{(t)}).}$

Thus, setting ${\displaystyle x'_{s'}}$ so as to minimize the resulting value of ${\displaystyle E[F|x^{(t)}]}$ will guarantee that ${\displaystyle E[F|x^{(t)}]\leq E[F|x^{(t-1)}]}$. This is what the algorithm will do.

In detail, what does this mean? Considered as a function of ${\displaystyle x'_{s'}}$ (with all other quantities fixed) ${\displaystyle E[F|x^{(t)}]}$ is a linear function of ${\displaystyle x'_{s'}}$, and the coefficient of ${\displaystyle x'_{s'}}$ in that function is

${\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}~-~\sum _{e\in s'\cap {\mathcal {U}}_{t-1}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}$

Thus, the algorithm should set ${\displaystyle x'_{s'}}$ to 0 if this expression is positive, and 1 otherwise. This gives the following algorithm.

input: set system ${\displaystyle {\mathcal {S}}}$, universe ${\displaystyle {\mathcal {U}}}$, cost vector ${\displaystyle c}$

output: set cover ${\displaystyle x'}$ (a solution to the standard integer linear program for set cover)

1. Compute a min-cost fractional set cover ${\displaystyle x^{*}}$ (an optimal solution to the LP relaxation).
2. Let ${\displaystyle \lambda \leftarrow \ln(2|{\mathcal {U}}|)}$. Let ${\displaystyle p_{s}\leftarrow \min(\lambda x_{s}^{*},1)}$ for each ${\displaystyle s\in {\mathcal {S}}}$.
3. For each ${\displaystyle s'\in {\mathcal {S}}}$ do:
   1. Let ${\displaystyle {\mathcal {S}}\leftarrow {\mathcal {S}}-\{s'\}}$.   (${\displaystyle {\mathcal {S}}}$ contains the not-yet-decided sets.)
   2. If    ${\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}>\sum _{e\in s'\cap {\mathcal {U}}}\prod _{s\in {\mathcal {S}},s\ni e}(1-p_{s})}$

      then set ${\displaystyle x'_{s}\leftarrow 0}$,

      else set ${\displaystyle x'_{s}\leftarrow 1}$ and ${\displaystyle {\mathcal {U}}\leftarrow {\mathcal {U}}-s'}$.

        (${\displaystyle {\mathcal {U}}}$ contains the not-yet-covered elements.)

4. Return ${\displaystyle x'}$.

The algorithm above returns a set cover ${\displaystyle x'}$ of cost at most ${\displaystyle 2\ln(2|{\mathcal {U}}|)}$ times the minimum cost of any (fractional) set cover.

The algorithm ensures that the conditional expectation of ${\displaystyle F}$, ${\displaystyle E[F\,|\,x^{(t)}]}$, does not increase at each iteration. Since this conditional expectation is initially less than 1 (as shown previously), the algorithm ensures that the conditional expectation stays below 1. Since the conditional probability of failure is at most the conditional expectation of ${\displaystyle F}$, in this way the algorithm ensures that the conditional probability of failure stays below 1. Thus, at the end, when all choices are determined, the algorithm reaches a successful outcome. That is, the algorithm above returns a set cover ${\displaystyle x'}$ of cost at most ${\displaystyle 2\ln(2|{\mathcal {U}}|)}$ times the minimum cost of any (fractional) set cover.

In the example above, the algorithm was guided by the conditional expectation of a random variable ${\displaystyle F}$. In some cases, instead of an exact conditional expectation, an upper bound (or sometimes a lower bound) on some conditional expectation is used instead. This is called a pessimistic estimator.