Approximating quadratic programming with bound constraints

Yinyu Ye

We consider the problem of approximating the global maximum of a quadratic program (QP) with $n$ variables subject to bound constraints. Based on the results of Goemans and Williamson \cite{Goemans} and Nesterov \cite{Nesterov}, we show that a $4/7$ approximate solution can be obtained in polynomial time.

Working Paper, Department of Management Science, The University of Iowa, Iowa City, March 1997.

Contact: yinyu-ye@uiowa.edu


 [DVI]  [PS]  [IP PAGE]  [SEARCH AGAIN]