“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.” – from Wikipedia

In the following we prove the correctness of randomized rounding on LP, given the optimal value.

This work was done in collaboration with Romolo Marotta during preparation for the exam of Theoretical Computer Science at University “La Sapienza” – Italy