Next: MINIMUM GENERALIZED 0-1 ASSIGNMENT Up: Mathematical Programming Previous: MINIMUM COVERING INTEGER PROGRAMMING Index

### MAXIMUM QUADRATIC PROGRAMMING

- INSTANCE: Positive integer n, set of linear constraints, given as an m x n-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 [64].

- 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 [64]. Note that these problems are known to be solvable in polynomial space but are not known to be in NP.

- Garey and Johnson: MP2