dc.contributor.author Vavasis, Stephen A. en_US dc.date.accessioned 2007-04-23T17:50:54Z dc.date.available 2007-04-23T17:50:54Z dc.date.issued 1990-12 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1172 en_US dc.identifier.uri https://hdl.handle.net/1813/7012 dc.description.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$. en_US dc.format.extent 1467894 bytes dc.format.extent 328032 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title Approximation Algorithms for Concave Quadratic Programming en_US dc.type technical report en_US
﻿