  Binary quadratic programming problems have attracted much attention in the
last few decades due to their potential applications. This type of problems are
NP-hard in general, and still considered a challenge in the design of efficient
approximation algorithms for their solutions. The purpose of this paper is to
investigate the approximability for a class of such problems where the
constraint matrices are {\it completely positive} and have low {\it cp-rank}.
In the first part of the paper, we show that a completely positive rational
factorization of such matrices can be computed in polynomial time, within any
desired accuracy. We next consider binary quadratic programming problems of the
following form: Given matrices $Q_1,...,Q_n\in\mathbb{R}_+^{n\times n}$, and a
system of $m$ constrains $x^TQ_ix\le C_i^2$ ($x^TQ_ix\ge C_i^2$), $i=1,...,m$,
we seek to find a vector $x^*\in \{0,1\}^n$ that maximizes (minimizes) a given
function $f$. This class of problems generalizes many fundamental problems in
discrete optimization such as packing and covering integer programs/knapsack
problems, quadratic knapsack problems, submodular maximization, etc. We
consider the case when $m$ and the cp-ranks of the matrices $Q_i$ are bounded
by a constant.
  Our approximation results for the maximization problem are as follows. For
the case when the objective function is nonnegative submodular, we give an
$(1/4-\epsilon)$-approximation algorithm, for any $\epsilon>0$; when the
function $f$ is linear, we present a PTAS. We next extend our PTAS result to a
wider class of non-linear objective functions including quadratic functions,
multiplicative functions, and sum-of-ratio functions. The minimization problem
seems to be much harder due to the fact that the relaxation is {\it not}
convex. For this case, we give a QPTAS for $m=1$.
