In computer science and operations research, randomized rounding
is a widely-used approach for designing and analyzing approximation algorithms.
Many combinatorial optimization problems are computationally intractable to solve exactly (to optimality). 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.
The basic idea of randomized rounding is to convert an optimal solution of a relaxation of the problem into an approximately-optimal solution to the original problem. The resulting algorithm is usually analyzed using the probabilistic method.
Overview
The basic approach has three steps: Formulate the problem to be solved as an integer linear program (ILP). Compute an optimal fractional solution to the linear programming relaxation (LP) of the ILP. Round the fractional solution of the LP to an integer solution of the ILP.
(Although the approach is most commonly applied with linear programs, other kinds of relaxations are sometimes used. 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. Familiarity with linear programming, in particular modelling using linear programs and integer linear programs, is required. For many problems, there is a natural integer linear program that works well, such as in the Set Cover example below. (The integer linear program should have a small integrality gap; indeed randomized rounding is often used to prove bounds on integrality gaps.)
In the second step, the optimal fractional solution can typically be computed
in polynomial time
using any standard linear programming algorithm.
In the third step, the fractional solution must be converted into an integer solution (and thus a solution to the original problem). This is called rounding the fractional solution. The resulting integer solution should (provably) have cost not much larger than the cost of the fractional solution. This will ensure that the cost of the integer solution is not much larger than the cost of the optimal integer solution.
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. In this context, one uses such arguments to show the following: Given any fractional solution of the LP, with positive probability the randomized rounding process produces an integer solution that approximates according to some desired criterion.
Finally, to make the third step computationally efficient, one either shows that approximates with high probability (so that the step can remain randomized) or one derandomizes the rounding step, typically using the method of conditional probabilities. The latter method converts the randomized rounding process into an efficient deterministic process that is guaranteed to reach a good outcome.
Example: the set cover problem
The following example illustrates how randomized rounding can be used to design an approximation algorithm for the set cover problem. Fix any instance of set cover over a universe .
Computing the fractional solution
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 to LP using any standard linear programming algorithm. This takes time polynomial in the input size. The feasible solutions to LP are the vectors that assign each set a non-negative weight , such that, for each element , covers -- the total weight assigned to the sets containing is at least 1, that is,
The optimal solution is a feasible solution whose cost
is as small as possible. Note that any set cover for gives a feasible solution (where for , otherwise). The cost of this equals the cost of , that is,
In other words, the linear program LP is a relaxation of the given set-cover problem.
Since has minimum cost among feasible solutions to the LP, the cost of is a lower bound on the cost of the optimal set cover.