A max-cut formulation of 0/1 programs

We show that the linear or quadratic 0/1 program[P:quadmin cTx+xTFx : :A,x =b;:x∈0,1n,]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 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.