Randomized rounding

Within computer science and operations research, many combinatorial optimization problems are computationally intractable to solve exactly (to optimality). Many such problems do admit fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input.

Randomized rounding (Raghavan & Tompson 1987) is a widely used approach for designing and analyzing such approximation algorithms. The basic idea is to use the probabilistic method to convert an optimal solution of a relaxation of the problem into an approximately optimal solution to the original problem.

The basic approach has three steps:

(Although the approach is most commonly applied with linear programs, other kinds of relaxations are sometimes used. For example, see Goeman's and Williamson's semi-definite programming-based Max-Cut approximation algorithm.)

The challenge in the first step is to choose a suitable integer linear program. Familiarity with linear programming is required, in particular, familiarity with how to model problems using linear programs and integer linear programs. But, 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.

...
Wikipedia