INSTANCE:
Positive integer n, set of linear constraints, given as an
-matrix A and an m-vector b, specifying a
region
by
.
SOLUTION:
A multivariate polynomial
of total degree at most 2.
MEASURE:
The maximum value of f in the region specified by the linear constants,
i.e.,
.
Bad News:
Does not admit a -approximation for any constant
[69].
Comment:
A -approximation algorithm finds a solution that differs from the
optimal solution by at most the value
.
Variation in which we look for a polynomial f of any degree
does not admit a -approximation for
for some
[69].
Note that these problems are known to be solvable in polynomial space but
are not known to be in NP.