Approximating quadratic programming with quadratic constraints

Yinyu Ye

We consider the problem of approximating the global maximum of a quadratic program (QP) subject to bound and (simple) quadratic constraints. Based on several early results, we further show that a $4/7$-approximate solution can be obtained in polynomial time.

Working Paper, Department of Management Science, The University of Iowa, Iowa City, IA 52242, April, 1997.