CONVEX RELAXATIONS OF (0,1)-QUADRATIC PROGRAMMING

We consider three parametric relaxations of the (0, 1)-quadratic progr amming problem. These relaxations are to: quadratic maximization over simple box constraints, quadratic maximization over the sphere, and th e maximum eigenvalue of a bordered matrix. When minimized over the par ameter, each of the relaxations provides an upper bound on the origina l discrete problem. Moreover, these bounds are efficiently computable. Our main result is that, surprisingly, all three bounds are equal.