{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T01:13:21Z","timestamp":1780535601391,"version":"3.54.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1998,3,1]],"date-time":"1998-03-01T00:00:00Z","timestamp":888710400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,3,1]],"date-time":"1998-03-01T00:00:00Z","timestamp":888710400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[1998,3]]},"DOI":"10.1023\/a:1009739827008","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T22:50:41Z","timestamp":1040597441000},"page":"29-50","source":"Crossref","is-referenced-by-count":48,"title":["Approximation Algorithms for Quadratic Programming"],"prefix":"10.1007","volume":"2","author":[{"given":"Minyue","family":"Fu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhi-Quan","family":"Luo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"157586_CR1","first-page":"429","volume":"69","author":"M. Bellare","year":"1995","unstructured":"M. Bellare and P. Rogaway, \u201cThe complexity of approximating a nonlinear program,\u201d Mathematical Programming, vol. 69, pp. 429-442, 1995.","journal-title":"Mathematical Programming"},{"key":"157586_CR2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970777","volume-title":"Linear Matrix Inequalities in System and Control Theory","author":"S. Boyd","year":"1994","unstructured":"S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix Inequalities in System and Control Theory, SIAM: Philadelphia, 1994."},{"key":"157586_CR3","first-page":"71","volume-title":"Numerical Optimization","author":"M.R. Celis","year":"1984","unstructured":"M.R. Celis, J.E. Dennis and R.A. Tapia, \u201cA trust region strategy for nonlinear equality constrained optimization,\u201d in Numerical Optimization, P.T. Boggs, R. Byrd, and R. Schnabel (Eds.), SIAM Publication: Philadelphia, 1984, pp. 71-82."},{"key":"157586_CR4","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0024-3795(68)90052-9","volume":"1","author":"R.W. Cottle","year":"1968","unstructured":"R.W. Cottle and G.B. Dantzig, \u201cComplementary pivot theory in mathematical programming,\u201d Linear Algebra and its Applications, vol. 1, pp. 103-125, 1968.","journal-title":"Linear Algebra and its Applications"},{"key":"157586_CR5","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF01211520","volume":"7","author":"G.E. Coxson","year":"1994","unstructured":"G.E. Coxson and C.L. DeMarco, \u201cThe computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix,\u201d Mathematics of Control, Signals, and Systemsvol. 7, pp. 279-292, 1994.","journal-title":"Mathematics of Control, Signals, and Systems"},{"key":"157586_CR6","volume-title":"Numerical Methods for Unconstrained Optimization and Nonlinear Equations","author":"J.E. Dennis Jr.","year":"1983","unstructured":"J.E. Dennis, Jr. and R.E. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall: NJ, 1983."},{"key":"157586_CR7","series-title":"Technical report","volume-title":"Semidefinite programming relaxation for nonconvex quadratic programs","author":"T. Fujie","year":"1995","unstructured":"T. Fujie and M. Kojima, \u201cSemidefinite programming relaxation for nonconvex quadratic programs, Technical report CORR 95-12, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, 1995."},{"key":"157586_CR8","volume-title":"Computers and Intractability, A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1968","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-completeness, Freeman: New York, 1968."},{"key":"157586_CR9","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0902016","volume":"2","author":"D.M. Gay","year":"1981","unstructured":"D.M. Gay, \u201cComputing optimal locally constrained steps,\u201d SIAM J. Sci. Statis. Comput., vol. 2, pp. 186-197, 1981.","journal-title":"SIAM J. Sci. Statis. Comput."},{"key":"157586_CR10","volume-title":"Practical Optimization","author":"P.E. Gill","year":"1981","unstructured":"P.E. Gill, W.M. Murray, and M.H. Wright, Practical Optimization, Academic Press: London, 1981."},{"key":"157586_CR11","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01581082","volume":"57","author":"A.P. Kamath","year":"1992","unstructured":"A.P. Kamath, N.K. Karmarkar, K.G. Ramakrishnan, and M.G.C. Resende, \u201cA continuous approach to inductive inference,\u201d Mathematical Programming, vol. 57, pp. 215-238, 1992.","journal-title":"Mathematical Programming"},{"key":"157586_CR12","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1090\/qam\/10666","volume":"2","author":"K. Levenberg","year":"1963","unstructured":"K. Levenberg, \u201cA method for the solution of certain nonlinear problems in least squares,\u201d Quarterly Appl. Math., vol. 2, pp. 164-168, 1963.","journal-title":"Quarterly Appl. Math."},{"key":"157586_CR13","unstructured":"Z.-Q. Luo and J. Sun, \u201cAn analytic center based column generation algorithm for the convex quadratic feasibility problem,\u201d Manuscript, Department of Electrical and Computer Engineering, McMaster University, November, 1995."},{"key":"157586_CR14","first-page":"431","volume":"11","author":"D.W. Marquardt","year":"1963","unstructured":"D.W. Marquardt, \u201cAn algorithm for least-squares estimation of nonlinear parameters,\u201d J. SIAM, vol. 11, pp. 431- 441, 1963.","journal-title":"J. SIAM"},{"key":"157586_CR15","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1137\/0804009","volume":"4","author":"J.M. Martinez","year":"1994","unstructured":"J.M. Martinez, \u201cLocal minimizers of quadratic functions on Euclidean balls and spheres,\u201d SIAM J. Optimization, vol. 4, pp. 159-176, 1994.","journal-title":"SIAM J. Optimization"},{"key":"157586_CR16","volume-title":"Numerical Analysis","author":"J.J. Mor\u00e9","year":"1977","unstructured":"J.J. Mor\u00e9, \u201cThe Levenberg-Marquardt algorithm: implementation and theory,\u201d in Numerical Analysis, G.A. Watson (Ed.), Springer-Verlag: New York, 1977."},{"key":"157586_CR17","volume-title":"Linear Complementarity, Linear and Nonlinear Programming","author":"K.G. Murty","year":"1988","unstructured":"K.G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Heldermann: Verlag, Berlin, 1988."},{"key":"157586_CR18","first-page":"149","volume":"69","author":"Y. E. Nesterov","year":"1995","unstructured":"Yu. E. Nesterov, \u201cCutting plane algorithms from analytic centers: Efficiency estimates,\u201d Mathematical Programming B, vol. 69, pp. 149-176, 1995.","journal-title":"Mathematical Programming B"},{"key":"157586_CR19","volume-title":"Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms","author":"Y. E. Nesterov","year":"1993","unstructured":"Yu. E. Nesterov and A.S. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms, SIAM Publications: Philadelphia, 1993."},{"key":"157586_CR20","doi-asserted-by":"crossref","unstructured":"P.M. Pardalos and J.B. Rosen, Constrained Global Optimization: Algorithms and Applications, Springer-Verlag, Lecture Notes in Computer Sciences, vol. 268, 1987.","DOI":"10.1007\/BFb0000035"},{"key":"157586_CR21","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01100205","volume":"7","author":"S. Polijak","year":"1995","unstructured":"S. Polijak, F. Rendl, and H. Wolkowicz, \u201cA recipe for semidefinite relaxation for 0-1 quadratic programming,\u201d Journal of Global Optimization, vol. 7, pp. 51-73, 1995.","journal-title":"Journal of Global Optimization"},{"key":"157586_CR22","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF01588787","volume":"49","author":"M.J.D. Powell","year":"1991","unstructured":"M.J.D. Powell and Y. Yuan, \u201cA trust region algorithm for equality constrained optimization,\u201d Mathematical Programming, vol. 49, pp. 189-211, 1991.","journal-title":"Mathematical Programming"},{"key":"157586_CR23","series-title":"CORR Report","volume-title":"Asemidefinite framework for trust region subproblems with applications to large scale minimization","author":"F. Rendl","year":"1994","unstructured":"F. Rendl and H. Wolkowicz, \u201cAsemidefinite framework for trust region subproblems with applications to large scale minimization,\u201d CORR Report 94-32, Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada, 1994."},{"key":"157586_CR24","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S. Sahni","year":"1974","unstructured":"S. Sahni, \u201cComputationally related problems,\u201d SIAM J. Compu., vol. 3, pp. 262-279, 1974.","journal-title":"SIAM J. Compu."},{"key":"157586_CR25","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons: New York, 1986."},{"key":"157586_CR26","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0719026","volume":"19","author":"D.C. Sorenson","year":"1982","unstructured":"D.C. Sorenson, \u201cNewton's method with a model trust region modification,\u201d SIAM J. Numer. Anal., vol. 19, pp. 409-426, 1982.","journal-title":"SIAM J. Numer. Anal."},{"key":"157586_CR27","volume-title":"Nonlinear Optimization: Complexity Issues","author":"S.A. Vavasis","year":"1991","unstructured":"S.A. Vavasis, Nonlinear Optimization: Complexity Issues, Oxford Science: New York, 1991."},{"key":"157586_CR28","volume-title":"Complexity in Numerical Optimization","author":"S.A. Vavasis","year":"1993","unstructured":"S.A. Vavasis, \u201cPolynomial time weak approximation algorithms for quadratic programming,\u201d in Complexity in Numerical Optimization, C.A. Floudas and P.M. Pardalos (Eds.), World Scientific: NJ, 1993."},{"key":"157586_CR29","series-title":"Technical Report","volume-title":"Proving polynomial time for sphere-constrained quadratic programming","author":"S.A. Vavasis","year":"1990","unstructured":"S.A. Vavasis and R. Zippel, \u201cProving polynomial time for sphere-constrained quadratic programming,\u201d Technical Report 90-1182, Department of Computer Science, Cornell University, Ithaca, NY, 1990."},{"key":"157586_CR30","unstructured":"V.A. Yakubovich, \u201cS-procedure in nonlinear control theory\u201d Vestnik Leningradskovo Universiteta, Seriya Matematika, pp. 62-77, 1971. (English translation in Vertnik Leningrad University, vol. 4, pp. 73-93, 1977)."},{"key":"157586_CR31","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF01580903","volume":"56","author":"Y. Ye","year":"1992","unstructured":"Y. Ye, \u201cOn affine scaling algorithms for nonconvex quadratic programming,\u201d Mathematical Programming, vol. 56, pp. 285-300, 1992.","journal-title":"Mathematical Programming"},{"key":"157586_CR32","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1006\/jcom.1994.1014","volume":"10","author":"Y. Ye","year":"1994","unstructured":"Y. Ye, \u201cCombining binary search and Newton's method to compute real roots for a class of real functions,\u201d Journal of Complexity, vol. 10, pp. 271-280, 1994.","journal-title":"Journal of Complexity"},{"key":"157586_CR33","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01580852","volume":"47","author":"Y. Yuan","year":"1990","unstructured":"Y. Yuan, \u201cOn a subproblem of trust region algorithms for constrained optimization,\u201d Mathematical Programming, vol. 47, pp. 53-63, 1990.","journal-title":"Mathematical Programming"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009739827008.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009739827008\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009739827008.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:12:41Z","timestamp":1751281961000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009739827008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,3]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,3]]}},"alternative-id":["157586"],"URL":"https:\/\/doi.org\/10.1023\/a:1009739827008","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,3]]}}}