APPROXIMATION ALGORITHMS FOR QUADRATIC-PROGRAMMING

We consider the problem of approximating the global minimum of a gener al quadratic program (QP) with n variables subject to m ellipsoidal co nstraints. For m = 1, we rigorously show that an c-minimizer, where er ror epsilon is an element of (0, 1), can be obtained in polynomial tim e, meaning that the number of arithmetic operations is a polynomial in n, m, and log(1/epsilon). For m greater than or equal to 2, we presen t a polynomial-time (1 - 1/m(2))-approximation algorithm as well as a semidefinite programming relaxation for this problem. In addition, we present approximation algorithms for solving QP under the box constrai nts and the assignment polytope constraints.