##
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

Contact: yinyu-ye@uiowa.edu