Randomized rounding Created 2026-10-06 Updated 2026-11-05
Randomized rounding converts a solution of a continuous relaxation of a integer programming problem into a random discrete candidate. For fractional binary variables , independent Bernoulli random variables with preserve a linear objective in expectation: . They do not automatically preserve every constraint.
For example, satisfies , but independent rounding chooses both items with probability . A feasibility argument, rejection, repair, or a dependent rounding construction is therefore needed before this becomes an approximation algorithm. The objective bound and the feasibility guarantee are separate parts of its proof.
Gaussian hyperplane rounding uses a shared random hyperplane to produce a feasible sign vector for a semidefinite relaxation of binary quadratic optimization. Rademacher rounding for a semidefinite relaxation instead uses random signs in its construction. In both cases the distribution is chosen so that an expected objective bound can be related to the relaxation value.