MAXIMUM QUADRATIC PROGRAMMING

• INSTANCE: Positive integer n, set of linear constraints, given as an $m\times n$-matrix A and an m-vector b, specifying a region $S\subseteq R^n$ by $S=\{x\in [0,1]^n: Ax\le b\}$.

• SOLUTION: A multivariate polynomial $f(x_1,\ldots,x_n)$ of total degree at most 2.

• MEASURE: The maximum value of f in the region specified by the linear constants, i.e., $\max_{x\in S} f(x)$.

  
  

• Bad News: Does not admit a $\mu$-approximation for any constant $0<\mu<1$ [69].

• Comment: A $\mu$-approximation algorithm finds a solution that differs from the optimal solution by at most the value $\mu\left(\max_{x\in S} f(x)- \min_{x\in S} f(x)\right)$. Variation in which we look for a polynomial f of any degree does not admit a $\mu$-approximation for $\mu=1-n^{-\delta}$ for some $\delta>0$ [69]. Note that these problems are known to be solvable in polynomial space but are not known to be in NP.

• Garey and Johnson: MP2