randomized rounding
Deterministic LP rounding uses a fixed threshold — round up if the fraction is at least 1/2. Randomized rounding takes a more imaginative view: treat each fractional value as a PROBABILITY and flip a biased coin. If the LP says x_i = 0.7, set the variable to 1 with probability 0.7 and to 0 with probability 0.3. Coincidences of luck then conspire, on average, to give a solution close to the LP optimum — and the analysis uses expectation and tail bounds rather than a case-by-case argument.
Why does randomness help? Two reasons converge. First, linearity of expectation makes the expected cost trivial to compute: the expected contribution of variable i is exactly x_i (it becomes 1 with probability x_i), so the expected total cost is exactly the sum of x_i = LP-OPT. In one stroke, on average you pay precisely the LP value. Second, for satisfying constraints you reason about probabilities: in a covering problem, an edge or clause might be left uncovered with some small probability, and you bound that failure chance. The standard move is to round independently, then either repeat the random draw until all constraints hold, or scale the probabilities up slightly (round x_i = 1 with probability min(1, c * x_i) for a small factor c, like c = ln n) so that the chance any single constraint fails becomes tiny. A Chernoff or union bound then shows that, with high probability, ALL constraints are satisfied at once while the cost stays within a small factor of LP-OPT. For set cover this exact recipe reproduces the O(log n) guarantee.
Randomized rounding is a workhorse precisely because it is general and the math is clean: expectation handles cost, concentration inequalities handle feasibility, and the same template covers set cover, MAX-SAT, congestion-minimization routing, and more. The honest details: the algorithm is randomized, so its guarantee is 'in expectation' or 'with high probability', not a deterministic certainty on every run — though you can often repeat or derandomize to firm it up. And it is no magic: the integrality gap still bounds how good the rounded solution can be, since you are still rounding the same relaxation.
LP gives x = (0.7, 0.4, 0.9). Randomized rounding sets variable 1 to 1 with prob 0.7, variable 2 with prob 0.4, variable 3 with prob 0.9, independently. Expected cost = 0.7 + 0.4 + 0.9 = 2.0, exactly LP-OPT. To make sure constraints hold w.h.p., one scales the probabilities up by an O(log n) factor and applies a union bound over the constraints.
Treat each fraction as a coin-flip probability; expectation gives cost = LP-OPT, tail bounds give feasibility.
The guarantee is probabilistic, not absolute: a single run might violate a constraint or cost a bit more. You repair this by repeating, by scaling probabilities up (paying a log factor), or by derandomization — but the underlying integrality gap still caps the quality.