Show simple item record

dc.contributor.authorVavasis, Stephen A.en_US
dc.date.accessioned2007-04-23T17:50:54Z
dc.date.available2007-04-23T17:50:54Z
dc.date.issued1990-12en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1172en_US
dc.identifier.urihttps://hdl.handle.net/1813/7012
dc.description.abstractWe 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.extent1467894 bytes
dc.format.extent328032 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleApproximation Algorithms for Concave Quadratic Programmingen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics