# Randomized rounding

Randomly rounding a fractional LP solution to an integer solution.

The idea, introduced by Raghavan and Thompson in 1987, is to use the probabilistic method to round the solution of a linear program, converting it into an approximately optimal integer solution [3]. It’s a broadly useful technique. For many problems, randomized rounding yields algorithms with optimal approximation ratios (assuming PNP). This note describes randomized rounding and gives a few examples.

# Trivial example: Vertex Cover

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

1. Given any graph , compute a min-cost fractional vertex cover .
2. Return the random vertex cover where with probability .

The algorithm is a 2-approximation algorithm in expectation. Indeed, the rounded solution is a cover because for any edge one of its two endpoints must have , which forces into the cover . By inspection, the expected cost of is at most twice the cost of , which, since the cost of is a lower bound on the cost of the integral opt, is at most .

# 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 is used as basis for the probability distribution. This allows the cost of the rounded solution to be related to the cost of , and via that (since 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].

Rounding scheme.

Let be a minimum-cost fractional set cover (computed, say, by linear programming). Consider first the most natural scheme for rounding :

For each set independently, take with probability , otherwise take .

With this rounding scheme, the expected cost of the chosen sets is , the cost of the fractional cover. This is good. Unfortunately the coverage is not good in the worst case, when the set weights are relatively small, for then the probability that an element is not covered is about

$\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).$

Only a constant fraction of the elements will be covered in expectation. To increase the coverage, the standard rounding scheme scales up the rounding probabilities by an appropriate factor :

For each set independently, take with probability , otherwise take .

Scaling the probabilities increases the expected cost by , but makes coverage of all elements likely.

The next step is to show that this rounding scheme works with positive probability.

Lemma (existence proof).

Fix , where is the number of elements. With non-zero probability, the rounding scheme returns a set cover of cost at most (and thus, of cost times ).

(Note: with care the can be reduced to .)

Proof.

The output of the random rounding scheme has the desired properties as long as none of the following “bad” events occur:

• the cost is too high: it exceeds , or

• is not a cover: it fails to cover one of the elements .

Regarding the cost, the expectation of each is at most . By linearity of expectation, the expectation of is at most . Thus, by the Markov bound, the probability of the first bad event (the cost is too high) is at most .

For the remaining bad events (coverage of each element ), note that, for any given element , since , the probability that is not covered is

$\prod _{s\ni e} 1-p_ s {\, {<}\, }\prod _{s\ni e} \exp ({-}\lambda x^*_ s) {\, {=}\, }\exp \Big({-}\lambda \sum _{s\ni e} x^*_ s \Big) {\, {\le }\, }\exp ({-}\lambda ) {\, {=}\, }1/(2n).$

(The first step uses and , which is strict for . The last step uses the definition of .) Thus, for each of the elements, the probability that the element is not covered is less than . By the naive union bound, the probability that one of the bad events happens is less than . Thus, with positive probability there are no bad events and is a set cover of cost at most .

# Deconstructing the Set Cover existence proof to find Q

The argument above shows the existence of a set cover of cost ). The next step is to apply the method of conditional probabilities to the existence proof. The resulting algorithm will consider each set in turn, and set to either 0 or 1. Instead of setting randomly based on , it will set 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

$Q = \frac{c\cdot \tilde x}{2\lambda c\cdot x^*} {\, {+}\, }n_ m$

where is the number of elements left uncovered at the end that is, is the size of the set .

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

# Algorithm via the method of conditional probabilities

The algorithm will choose each set to keep the conditional expectation of , given the choices made so far, below 1. Consider the state after the th choice. Let denote the sets considered so far — for each set , the value of has been set to 0 or 1; the values for the remaining sets have not yet been determined. The conditional expectation of , given this state, is

$\phi _ t ~ =~ \frac{\sum _{s\in S_ t} c_ s \tilde x_ s + \sum _{s\not\in S_ t} c_ s p_ s}{2\lambda c\cdot x^*} ~ {\, {+}\, }~ \sum _ e \prod _{s\in S_ t} (1-[e\in s] \tilde x_ s) \prod _{s\not\in S_ t} (1-[e\in s]p_ s).$

The algorithm will keep (the conditional expectation of ) below 1 by setting each to minimize the resulting value of . Let denote the th set. When the algorithm sets , each for has already been set. Considered as a function of just (with all other quantities fixed) the quantity is linear in . Let denote the set of elements not covered before is considered. The coefficient of in is

$\frac{c_{s’}}{2\lambda c\cdot x^*} {\, {-}\, }\sum _{e\in U}[e\in s’]\prod _{s\not\in S_ t} (1-[e\in s]p_ s).$

To minimize , if this coefficient is positive, then the algorithm sets to 0. Otherwise it sets to 1:

 input: set system , universe , cost vector output: set cover 1. Compute min-cost fractional set cover . 2. Take and set for each . 3. For each do: 4. Let . … contains the not-yet-decided sets. 5. If   then set , else set and . 6. Return .

By ensuring at each step, the algorithm guarantees an outcome with , so that has cost at most and covers all elements:

Lemma (rounding algorithm approximation guarantee).

The algorithm above returns a set cover of cost at most times the minimum cost of any (fractional) set cover.

# Randomized rounding without solving the linear program

The algorithm’s choice for each depends intrinsically on the individual values within . (For example, if each element is contained in some not-yet-considered set with , then will not be added to the cover even if .) 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 . Thus, the algorithm can compute the approximate cover without first computing . You can read more about that here.

## Related

• Textbooks:  [4, Sec.14.2],  [1, ch.4],  [5, ch.5] (online)

## Footnotes

1. (1) For an application of the Markov bound, (), the pessimistic estimator will be the conditional expectation of .
(2) For an application of the naive union bound () the pessimistic estimator will be the sum of the pessimistic estimators of the individual events.
(3) For a bad event whose probability is computed (or estimated) directly, the pessimistic estimator will be the conditional probability (or the corresponding estimate).

## Discussion

1. Can you please explain this line in last line of page 5 “By ensuring ϕt≤ϕt−1ϕt≤ϕt−1 at each step, the algorithm guarantees an outcome with Q≤E[Q]<1, so that x~ has cost at most 2ln(2n)c⋅x∗and covers all elements. "

- Arindam
2. That line summarizes the reasoning in the previous pages. To break it down, the proof of the lemma on page 2 explains why the randomized-rounding scheme (with non-zero probability) returns $\tilde x$ of at most that cost ($2\ln(2n) \,c\cdot x^*$). The discussion on page 4 explains that to find an outcome where $\tilde x$ achieves that cost bound, it’s enough to find an outcome where $Q$ (as defined there) is less than 1, and why $E[Q]< 1$. The discussion on page 5 explains why $\phi_t$ is the conditional expectation of $Q$ given the first $t$ choices. That page also sketches why the deterministic algorithm there, in each iteration $t$, makes a choice that ensures that $\phi_t$ is at most $\phi_{t-1}$, so that the algorithm keeps the conditional expectation of $Q$ below 1, and thus reaches an outcome where $Q<1$, so that $\tilde x$ achieves the desired cost bound. If these comments don't make much sense to you, try going over the background material, linked to at the top. Or, if you have a question about any one of these steps, please post it.

- Neal Post author