The paper considers •-approximation schemes for indefinite quadratic programming. It argues that such an approximation can be found in polynomial time for fixed • and t, where t denotes the number of negative eigenvalues of the quadratic term. The present algorithm is polynomial in 1/• for fixed t, and exponential in t for fixed •. The paper next looks at the special case of knapsack problems, showing that a more efficient (polynomial in t) approximation algorithm exists.
