In computer science and operations research, randomized rounding[1] is a widely used approach for designing and analyzing approximation algorithms.
For such problems, randomized rounding can be used to design fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input.
For example, see Goemans' and Williamson's semidefinite programming-based Max-Cut approximation algorithm.)
In the first step, the challenge is to choose a suitable integer linear program.
For many problems, there is a natural integer linear program that works well, such as in the Set Cover example below.
In the second step, the optimal fractional solution can typically be computed in polynomial time using any standard linear programming algorithm.
The main technique used to do the third step (rounding) is to use randomization, and then to use probabilistic arguments to bound the increase in cost due to the rounding (following the probabilistic method from combinatorics).
Therein, probabilistic arguments are used to show the existence of discrete structures with desired properties.
The following example illustrates how randomized rounding can be used to design an approximation algorithm for the set cover problem.
For step 1, let IP be the standard integer linear program for set cover for this instance.
For step 2, let LP be the linear programming relaxation of IP, and compute an optimal solution
, that is, In other words, the linear program LP is a relaxation of the given set-cover problem.
is a lower bound on the cost of the optimal set cover.
In step 3, we must convert the minimum-cost fractional set cover
of the random rounding scheme has the desired properties as long as none of the following "bad" events occur: The expectation of each
The lemma above shows the existence of a set cover of cost
In this context our goal is an efficient approximation algorithm, not just an existence proof, so we are not done.
With this modification, repeating the random rounding step a few times is enough to ensure a successful outcome with high probability.
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 deterministic algorithm emulates the randomized rounding scheme: it considers each set
That proof implicitly bounds the probability of failure by the expectation of the random variable where is the set of elements left uncovered at the end.
may appear a bit mysterious, but it mirrors the probabilistic proof in a systematic way.
comes from applying Markov's inequality to bound the probability of the first bad event (the cost is too high).
The second term counts the number of bad events of the second kind (uncovered elements).
must cover all the elements and have cost meeting the desired bound from the lemma.
Note that the argument above is implicit already in the proof of the lemma, which also shows by calculation that
So, what about the conditional probability of failure as the rounding step iterates through the sets?
(a solution to the standard integer linear program for set cover) The algorithm ensures that the conditional expectation of
Thus, at the end, when all choices are determined, the algorithm reaches a successful outcome.
The randomized rounding step differs from most applications of the probabilistic method in two respects: