Bipartite binary quadratic optimization
= Bipartite binary quadratic optimization
For a real rectangular <matrix> $S$, maximize $p^TSq$ over separate sign choices for $p$ and $q$. With $x=(p,q)$, the symmetric block <matrix> $A=\tfrac12\begin{pmatrix}0&S\\S^T&0\end{pmatrix}$ satisfies $x^TAx=p^TSq$. Its zero diagonal blocks allow the <Krivine rounding scheme> to linearize the cross-block expected objective.