From fractions to decisions
Many optimization problems demand integer decisions, such as choosing whether to include each item, which makes them hard. Randomized rounding relaxes the integer requirement, solves the easier fractional version, then converts the fractions back to integers using randomness.
The two steps
First, solve the linear relaxation, allowing each decision variable to take any value between zero and one. This gives an optimal fractional solution and a lower bound on the true cost.
Second, round each variable to one with probability equal to its fractional value, independently.
- A variable at three quarters becomes one about three quarters of the time.
- The expected integer cost matches the fractional optimum.
Why it works
Because each variable is set to one with its own fraction as the probability, the expected value of the rounded solution equals the fractional objective. Concentration arguments then show the random outcome is close to that expectation, so constraints are usually satisfied and the cost stays near optimal.
- Repeat the rounding until a feasible solution appears.
- This yields strong approximation guarantees for problems like set cover.
Key idea
Randomized rounding solves the fractional relaxation of a hard integer problem, then sets each variable to one with probability equal to its fraction, so the expected cost matches the optimum and concentration keeps the rounded solution near feasible and cheap.