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 sciencetechnical 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