Abstract
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]
n
. The original approaches (complementation, majorization and linearization) were introduced by Hammer, Hansen and Simeone [9]. The generalization in this paper yields three upper bounds,
C
k
,
M
k
and
L
k
for each integer
k ⩾ 2, where
C
n
=
L
n
=
M
n
is the maximum of
f, and
C
2 =
L
2 =
M
2 is the roof duality bound studied in [9]. It is proved that
C
k
=
M
k
=
L
k
for all values of
k.