  We consider the problem of approximating Quadratic O-1 Integer Programs with
bounded number of constraints and non-negative constraint matrix entries, which
we term as PIQP.
  We describe and analyze a randomized algorithm based on a program with
hyperbolic constraints (a Second-Order Cone Programming -SOCP- formulation)
that achieves an approximation ratio of $O(a_{max} \frac{n}{\beta(n)})$, where
$a_{max}$ is the maximum size of an entry in the constraint matrix and
$\beta(n) \leq \min_i{W_i} $, where $W_i$ are the constant terms that define
the constraint inequalities. We note that by appropriately choosing $\beta(n)$
the randomized algorithm, when combined with other algorithms that achieve good
approximations for smaller values of $ W_i$, allows better algorithms for the
complete range of $W_i$. This, together with a greedy algorithm, provides a
$O^*(a_{max} n^{1/2} )$ factor approximation, where $O^*$ hides logarithmic
terms. Our solution is achieved by a randomization of the optimal solution to
the relaxed version of the hyperbolic program. We show that this solution
provides the approximation bounds using concentration bounds provided by
Chernoff-Hoeffding and Kim-Vu.
