= Bipartite sign rounding bound
For <bipartite binary quadratic optimization>, if $v^*$ is the sign optimum and $p^*_{\rm SDP}$ its <semidefinite relaxation of binary quadratic optimization> value, then $c_Kp^*_{\rm SDP}\leq v^*\leq p^*_{\rm SDP}$. The upper bound follows from rank-one lifting. For the lower bound, <Krivine rounding scheme> preprocessing followed by <Gaussian hyperplane rounding> has expected objective exactly $c_Kp^*_{\rm SDP}$, and every rounded <vector> is feasible. Some outcome reaches at least this <expectation>. No <independence> of rounded coordinates or <positive semidefiniteness> of the original bipartite objective is needed.
Back to article page
