Randomized Rounding




Randomized rounding is a tool which has been successfully
applied to obtain "good" approximations to optimal solutions of some NP-hard
discrete optimization problems. It is a way of converting a fractional
solution to a discrete one without compromising too much on the quality
of the solution. We will illustrate this tool with a few examples.