Consider the following program: \begin{align} \max_x ~& x^TQx \ \mbox{s.t.} ~& Ax \geq b \end{align} where $ Q$ is a symmetric (possibly indefinite) matrix and the inequality is element-wise and constrains feasible solutions to a convex polytope.

This is NP-hard to solve, but **what are known approximation results?**

A relevant result is given by (Kough 1979). It is shown that this program can be optimized using Benders’ decomposition to within $ \epsilon$ of the optimum. However, the paper does not seem to clearly specify what this means, or the complexity of the procedure.

I believe the $ \epsilon$ -approximation is in the usual sense employed in the field of mathematical programming, that is, is $ OPT$ is the optimal value of the program, $ ALG$ is the result of the above procedure and $ MIN$ is the minimal value attainable by a feasible solution, $ $ \frac{ALG-MIN}{OPT-MIN} \geq (1-\epsilon). $ $ Or something of the sort.

Questions:

- Is the mentioned procedure a polynomial-time algorithm?
- Are there known polynomial-time algorithms yielding approximations to the above program in the traditional sense, i.e. $ ALG \geq \alpha OPT $ for some $ \alpha < 1$ , constant or not.

Kough, Paul F. “The indefinite quadratic programming problem.” Operations Research 27.3 (1979): 516-533.