A max-cut formulation of 0/1 programs

We show that the linear or quadratic 0/1 program$$P:\min \{c^{T}x+x^{T}Fx:Ax=b;x\in \{0,1{\}}^n\},$$can be formulated as a MAX-CUT problem whose associated graph is simply related to the matrices $\text{F}$ and ${\text{A}}^T\text{A}$.Hence the whole arsenal of approximation techniques for MAX-CUT can be applied. We also compare the lower boundof the resulting semidefinite (or Shor) relaxation with that of the standard LP-relaxation and the first semidefinite relaxationsassociated with the Lasserre hierarchy and the copositive formulations of $P$.