## Approximation algorithms for quadratic programming

### Minyue Fu, Zhi-Quan Luo and Yinyu Ye

We consider the problem of approximating the global minimum of a general quadratic
program (QP) with $n$ variables subject to $m$ ellipsoidal constraints. For $m=1$, we
rigorously show that an $\epsilon$-minimizer, where error $\epsilon\in (0,1)$, can be
obtained in polynomial time, meaning that the number of arithmetic operations is a
polynomial in $n$, $m$, and $\log(1/\epsilon)$. For $m\ge 2$, we present a polynomial-time
$(1-\frac{1}{m^2})$-approximation algorithm as well as a semidefinite programming
relaxation for this problem. In addition, we present approximation algorithms for solving
QP under the box constraints and the assignment polytope constraints.

Manuscript, Department of Electrical and Computer Engineering, McMaster University,
Hamilton, Ontario, CANADA L8S 4K1

Contact: luozq@mcmail.cis.mcmaster.ca