Approximating quadratic optimization with linear and boolean constraints

Yinyu Ye

We consider approximating the global maximum of a quadratic program (QP) subject to linear as well as boolean constraints. We define an $\epsilon$-approximate (boolean) solution as both $\epsilon$-feasible (to the linear constraints) and $\epsilon$-optimal. Based on several early results, we show that an expected $.6$-approximate solution can be generated in polynomial time. A better result, $.43$, is obtained when the graph partition problem is being solved.

Working Paper, Department of Management Sciences, The University of Iowa, IA, USA, August, 1997