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.

Contact: yinyu-ye@uiowa.edu


 [DVI]  [PS]  [IP PAGE]  [SEARCH AGAIN]