Upper-bounds for quadratic 0-1 maximization

In this paper, three different approaches are generalised to obtain upper bounds for the maximum of a quadratic pseudo-Boolean function f over {0,1}ⁿ. The original approaches (complementation, majorization and linearization) were introduced by Hammer, Hansen and Simeone. The generalization in this paper yields three upper bounds, Ck, Mk and Lk for each integer k≥2, where Cn=Ln=Mn is the maximum of f, and C2=L2=M2 is the roof duality bound studied in the Hammer, Hansen and Simeone paper. It is proved that Ck=Mk=Lk for all values of k.