Approximation Algorithms for Quadratic Programming |
| |
Authors: | Minyue Fu Zhi-Quan Luo Yinyu Ye |
| |
Institution: | (1) Department of Electrical and Computer Engineering, The University of Newcastle, Newcastle, NSW, 2308, Australia |
| |
Abstract: | We consider the problem of approximating the global minimum of a general quadratic program (QP) with n variables subject to m ellipsoidal constraints. For m=1, we rigorously show that an -minimizer, where error (0, 1), can be obtained in polynomial time, meaning that the number of arithmetic operations is a polynomial in n, m, and log(1/ ). For m 2, we present a polynomial-time (1-
)-approximation algorithm as well as a semidefinite programming relaxation for this problem. In addition, we present approximation algorithms for solving QP under the box constraints and the assignment polytope constraints. |
| |
Keywords: | quadratic programming global minimizer polynomial-time approximation algorithm |
本文献已被 SpringerLink 等数据库收录! |
|