Randomized rounding (source code)

= 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.