  Quadratic Programming (QP) is the well-studied problem of maximizing over
{-1,1} values the quadratic form \sum_{i \ne j} a_{ij} x_i x_j. QP captures
many known combinatorial optimization problems, and assuming the unique games
conjecture, semidefinite programming techniques give optimal approximation
algorithms. We extend this body of work by initiating the study of Quadratic
Programming problems where the variables take values in the domain {-1,0,1}.
The specific problems we study are
  QP-Ratio : \max_{\{-1,0,1\}^n} \frac{\sum_{i \not = j} a_{ij} x_i x_j}{\sum
x_i^2}, and Normalized QP-Ratio : \max_{\{-1,0,1\}^n} \frac{\sum_{i \not = j}
a_{ij} x_i x_j}{\sum d_i x_i^2}, where d_i = \sum_j |a_{ij}|
  We consider an SDP relaxation obtained by adding constraints to the natural
eigenvalue (or SDP) relaxation for this problem. Using this, we obtain an
$\tilde{O}(n^{1/3})$ algorithm for QP-ratio. We also obtain an
$\tilde{O}(n^{1/4})$ approximation for bipartite graphs, and better algorithms
for special cases. As with other problems with ratio objectives (e.g. uniform
sparsest cut), it seems difficult to obtain inapproximability results based on
P!=NP. We give two results that indicate that QP-Ratio is hard to approximate
to within any constant factor. We also give a natural distribution on instances
of QP-Ratio for which an n^\epsilon approximation (for \epsilon roughly 1/10)
seems out of reach of current techniques.
