= Randomized rounding
<Randomized rounding> converts a solution of a continuous relaxation of a <integer programming> problem into a random discrete candidate. For fractional binary variables $x_i\in[0,1]$, independent <Bernoulli random variables> $X_i$ with $P(X_i=1)=x_i$ preserve a linear objective in expectation: $\mathbb E\sum_i c_iX_i=\sum_i c_ix_i$. They do not automatically preserve every constraint.
For example, $x_1=x_2=1/2$ satisfies $x_1+x_2\leq1$, but independent rounding chooses both items with probability $1/4$. 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.
Back to article page