Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Approximation Algorithms for Concave Quadratic Programming
Authors: Vavasis, Stephen A.
Keywords: computer science
technical report
Issue Date: Dec-1990
Publisher: Cornell University
Abstract: We consider $\epsilon$-approximation schemes for concave quadratic programming. Because the existing definition of $\epsilon$-approximation for combinatorial optimization problems is inappropriate for nonlinear optimization, we propose a new definition for $\epsilon$-approximation. We argue that such an approximation can be found in polynomial time for fixed $\epsilon$ and $k$, where $k$ denotes the number of negative eigenvalues. Our algorithm is polynomial in 1/$\epsilon$ for fixed $k$, and superexponential in $k$ for fixed $\epsilon$.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
90-1172.pdf1.43 MBAdobe PDFView/Open
90-1172.ps320.34 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us