{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:24:55Z","timestamp":1759847095146},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1992,5,1]],"date-time":"1992-05-01T00:00:00Z","timestamp":704678400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1992,5]]},"DOI":"10.1007\/bf01581085","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T05:52:15Z","timestamp":1114667535000},"page":"279-311","source":"Crossref","is-referenced-by-count":61,"title":["Approximation algorithms for indefinite quadratic programming"],"prefix":"10.1007","volume":"57","author":[{"given":"Stephen A.","family":"Vavasis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","volume-title":"Dynamic Programming","author":"R.E. Bellman","year":"1957","unstructured":"R.E. Bellman,Dynamic Programming (Princeton University Press, Princeton, NJ, 1957)."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0167-6377(84)90010-5","volume":"3","author":"P. Brucker","year":"1984","unstructured":"P. Brucker, \u201cAn O(n) algorithm for quadratic knapsack problems,\u201dOperations Research Letters 3 (1984) 163\u2013166.","journal-title":"Operations Research Letters"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/nav.3800330106","volume":"33","author":"R.W. Cottle","year":"1986","unstructured":"R.W. Cottle, S.G. Duvall and K. Zikan, \u201cA Lagrangean relaxation algorithm for the constrained matrix problem,\u201dNaval Research Logistics Quarterly 33 (1986) 55\u201376.","journal-title":"Naval Research Logistics Quarterly"},{"key":"CR4","series-title":"Working Paper","volume-title":"Identifying the set of always active constraints in a system of linear inequalities by a single linear program","author":"R.M. Freund","year":"1985","unstructured":"R.M. Freund, R. Roundy, and M.J. Todd, \u201cIdentifying the set of always active constraints in a system of linear inequalities by a single linear program,\u201d Working Paper 1674-85, Sloan School of Management, MIT (Cambridge, MA, 1985)."},{"key":"CR5","volume-title":"Practical Optimization","author":"P.E. Gill","year":"1981","unstructured":"P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, London, 1981)."},{"key":"CR6","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1989","unstructured":"G.H. Golub and C.F. Van Loan,Matrix Computations (Johns Hopkins University Press, Baltimore, MD, 1989, 2nd ed.).","edition":"2nd ed."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1007\/BF01588328","volume":"18","author":"R. Helgason","year":"1980","unstructured":"R. Helgason, J. Kennington and H. Lall, \u201cA polynomially bounded algorithm for a singly constrained quadratic program,\u201dMathematical Programming 18 (1980) 338\u2013343.","journal-title":"Mathematical Programming"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J. Hershberger","year":"1989","unstructured":"J. Hershberger, \u201cFinding the upper envelope ofn line segments in O(n logn) time,\u201dInformation Processing Letters 33 (1989) 169\u2013174.","journal-title":"Information Processing Letters"},{"key":"CR9","first-page":"147","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing","author":"S. Kapoor","year":"1986","unstructured":"S. Kapoor and P.M. Vaidya, \u201cFast algorithms for convex quadratic programming and multicommodity flows,\u201d in:Proceedings of the 18th Annual ACM Symposium on Theory of Computing (ACM Press, New York, 1986) pp. 147\u2013159."},{"key":"CR10","first-page":"1049","volume":"248","author":"M.K. Kozlov","year":"1979","unstructured":"M.K. Kozlov, S.P. Tarasov and L.G. Ha\u010dijan, \u201cPolynomial solvability of convex quadratic programming,\u201dDoklad Akademii Nauk SSSR 248 (1979) 1049\u20131051. [Translated in:Soviet Mathematics Doklady 20 (1979) 1108\u20131111.]","journal-title":"Doklad Akademii Nauk SSSR"},{"key":"CR11","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970203","volume-title":"An Algorithmic Theory of Numbers, Graphs and Convexity","author":"L. Lov\u00e1sz","year":"1986","unstructured":"L. Lov\u00e1sz,An Algorithmic Theory of Numbers, Graphs and Convexity (SIAM, Philadelphia, PA, 1986)."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/BF01588800","volume":"49","author":"J.J. Mor\u00e9","year":"1991","unstructured":"J.J. Mor\u00e9 and S.A. Vavasis, \u201cOn the solution of concave knapsack problems,\u201dMathematical Programming 49 (1991) 397\u2013411.","journal-title":"Mathematical Programming"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"K.G. Murty","year":"1987","unstructured":"K.G. Murty and S.N. Kabadi, \u201cSome NP-complete problems in quadratic and nonlinear programming,\u201dMathematical Programming 39 (1987) 117\u2013129.","journal-title":"Mathematical Programming"},{"key":"CR14","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"A.S. Nemirovsky","year":"1983","unstructured":"A.S. Nemirovsky and D.B. Yudin,Problem Complexity and Method Efficiency in Optimization (Wiley, Chichester, 1983). [Translated by E.R. Dawson fromSlozhnost' Zadach i Effektivnost' Metodov Optimizatsii (1979).]"},{"key":"CR15","volume-title":"Combinatorial Optimization:Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization:Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982)."},{"key":"CR16","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0000035","volume-title":"Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science No. 268","author":"P.M. Pardalos","year":"1987","unstructured":"P.M. Pardalos and J.B. Rosen,Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science No. 268 (Springer, Berlin, 1987)."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF00120662","volume":"1","author":"P.M. Pardalos","year":"1990","unstructured":"P.M. Pardalos and S.A. Vavasis, \u201cQuadratic programming with one negative eigenvalue is NP-hard,\u201dJournal of Global Optimization 1 (1990) 15\u201322.","journal-title":"Journal of Global Optimization"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S. Sahni","year":"1974","unstructured":"S. Sahni, \u201cComputationally related problems,\u201dSIAM Journal on Computing 3 (1974) 262\u2013279.","journal-title":"SIAM Journal on Computing"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1109\/SFCS.1989.63499","volume-title":"Proceedings of the 30th Symposium on Foundations of Computer Science","author":"P.M. Vaidya","year":"1989","unstructured":"P.M. Vaidya, \u201cSpeeding-up linear programming using fast matrix multiplication (extended abstract),\u201dProceedings of the 30th Symposium on Foundations of Computer Science (ACM Press, New York, 1989) pp. 332\u2013337."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(90)90100-C","volume":"36","author":"S.A. Vavasis","year":"1990","unstructured":"S.A. Vavasis, \u201cQuadratic programming is in NP,\u201dInformation Processing Letters 36 (1990) 73\u201377.","journal-title":"Information Processing Letters"},{"key":"CR21","volume-title":"\u201cApproximation algorithms for indefinite quadratic programming,\u201d Technical Report 91-1228","author":"S.A. Vavasis","year":"1991","unstructured":"S.A. Vavasis, \u201cApproximation algorithms for indefinite quadratic programming,\u201d Technical Report 91-1228, Department of Computer Science, Cornell University (Ithaca, NY, 1991)."},{"key":"CR22","first-page":"3","volume-title":"Recent Advances in Global Optimization","author":"S.A. Vavasis","year":"1992","unstructured":"S.A. Vavasis, \u201cOn approximation algorithms for concave quadratic programming,\u201d in: C.A. Floudas and P.M. Pardalos, eds.,Recent Advances in Global Optimization (Princeton University Press, Princeton, NJ, 1992a) pp. 3\u201318."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01586048","volume":"54","author":"S.A. Vavasis","year":"1992","unstructured":"S.A. Vavasis, \u201cLocal minima for indefinite quadratic knapsack problems,\u201dMathematical Programming 54 (1992b) 127\u2013153.","journal-title":"Mathematical Programming"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01587086","volume":"44","author":"Y. Ye","year":"1989","unstructured":"Y. Ye and E. Tse, \u201cAn extension of Karmarkar's projective algorithm for convex quadratic programming,\u201dMathematical Programming 44 (1989) 157\u2013179.","journal-title":"Mathematical Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581085.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01581085\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T11:12:15Z","timestamp":1556881935000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01581085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,5]]},"references-count":24,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1992,5]]}},"alternative-id":["BF01581085"],"URL":"https:\/\/doi.org\/10.1007\/bf01581085","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,5]]}}}