Skip to main content


eCommons@Cornell

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

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7012
Title: Approximation Algorithms for Concave Quadratic Programming
Authors: Vavasis, Stephen A.
Keywords: computer science
technical report
Issue Date: Dec-1990
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1172
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$.
URI: http://hdl.handle.net/1813/7012
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