A MAX-CUT formulation of 0/1 programs

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