Approximation algorithms for indefinite quadratic programming

We consider-approximation schemes for indefinite quadratic programming. We argue that such an approximation can be found in polynomial time for fixed andt, wheret denotes the number of negative eigenvalues of the quadratic term. Our algorithm is polynomial in 1/ for fixedt, and exponential int for fixed. We next look at the special case of knapsack problems, showing that a more efficient (polynomial int) approximation algorithm exists.Part of this work was done while the author was visiting Sandia National Laboratories, Albuquerque, New Mexico, supported by the U.S. Department of Energy under contract DE-AC04-76DP00789. Part of this work was also supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.