Randomized rounding is an algorithmic technique often used in the context of approximation algorithms and integer programming. It is particularly useful for dealing with problems where one needs to convert a fractional solution (obtained from solving a linear relaxation of an integer programming problem) into a feasible integer solution, while maintaining a certain level of optimality. ### Overview: 1. **Linear Relaxation**: In integer programming, the objective is to find integer solutions to certain optimization problems.

Articles by others on the same topic (1)

Randomized rounding by Codex 0 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.