{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T06:42:51Z","timestamp":1770273771718,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2000,6,1]],"date-time":"2000-06-01T00:00:00Z","timestamp":959817600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2000,6,1]],"date-time":"2000-06-01T00:00:00Z","timestamp":959817600000},"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":[[2000,6]]},"DOI":"10.1023\/a:1009898604624","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T23:53:29Z","timestamp":1040601209000},"page":"197-215","source":"Crossref","is-referenced-by-count":79,"title":["A Semidefinite Programming Approach to the Quadratic Knapsack Problem"],"prefix":"10.1007","volume":"4","author":[{"given":"C.","family":"Helmberg","sequence":"first","affiliation":[]},{"given":"F.","family":"Rendl","sequence":"additional","affiliation":[]},{"given":"R.","family":"Weismantel","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"264574_CR1","doi-asserted-by":"crossref","unstructured":"E. Balas, \u201cDisjunctive programming: Cutting planes from logical conditions,\u201d in Nonlinear Programming, vol. 2, O.L. Mangasarian et al. (Eds.), Academic Press, 1975a, pp. 279\u2013312.","DOI":"10.1016\/B978-0-12-468650-2.50015-8"},{"key":"264574_CR2","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/BF01580440","volume":"8","author":"E. Balas","year":"1975","unstructured":"E. Balas, \u201cFacets of the knapsack polytope,\u201d Mathematical Programming, vol. 8, pp. 146\u2013164, 1975b.","journal-title":"Mathematical Programming"},{"key":"264574_CR3","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E. Balas","year":"1993","unstructured":"E. Balas, S. Ceria, and G. Cornuejols, \u201cA lift-and-project cutting plane algorithm for mixed 0=1 programs,\u201d Mathematical Programming, vol. 58, pp. 295\u2013324, 1993.","journal-title":"Mathematical Programming"},{"key":"264574_CR4","volume-title":"Updated semi-definite constraints","author":"E. Balas","year":"1994","unstructured":"E. Balas, S. Ceria, G. Cornuejols, and G. Pataki, \u201cUpdated semi-definite constraints,\u201d Technical Report, Carnegie Mellon University, Pittsburgh, USA, 1994."},{"key":"264574_CR5","series-title":"Working paper","volume-title":"Solving large-scale sparse semidefinite programs for combinatorial optimization","author":"S. Benson","year":"1997","unstructured":"S. Benson, Y. Ye, and X. Zhang, \u201cSolving large-scale sparse semidefinite programs for combinatorial optimization,\u201d Working paper, Department of Management Science, University of Iowa, IA, 52242, USA, Sept. 1997."},{"issue":"2","key":"264574_CR6","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1287\/ijoc.11.2.125","volume":"11","author":"A. Caprara","year":"1999","unstructured":"A. Caprara, D. Pisinger, and P. Toth, \u201cExact solution of quadratic knapsack problems,\u201d INFORMS J. on Comput., vol. 11, no. 2, pp. 125\u2013137, 1999.","journal-title":"INFORMS J. on Comput."},{"key":"264574_CR7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0012-365X(90)90056-N","volume":"79","author":"C. De Simone","year":"1989","unstructured":"C. De Simone, \u201cThe cut polytope and the boolean quadric polytope,\u201d Discrete Mathematics, vol. 79, pp. 71\u201375, 1989.","journal-title":"Discrete Mathematics"},{"issue":"2","key":"264574_CR8","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01580897","volume":"56","author":"M. Deza","year":"1992","unstructured":"M. Deza and M. Laurent, \u201cFacets for the cut cone I,\u201d Mathematical Programming, vol. 56, no. 2, pp. 121\u2013160, 1992a.","journal-title":"Mathematical Programming"},{"issue":"2","key":"264574_CR9","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF01580898","volume":"56","author":"M. Deza","year":"1992","unstructured":"M. Deza and M. Laurent, \u201cFacets for the cut cone II,\u201d Mathematical Programming, vol. 56, no. 2, pp. 161\u2013188, 1992b.","journal-title":"Mathematical Programming"},{"issue":"3","key":"264574_CR10","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF02592198","volume":"74","author":"C.E. Ferreira","year":"1996","unstructured":"C.E. Ferreira, A. Martin, C. De Souza, R. Weismantel, and L. Wolsey, \u201cFormulations and valid inequalities for the node capacitated graph partitioning problem,\u201d Mathematical Programming, vol. 74, no. 3, pp. 247\u2013267, 1996.","journal-title":"Mathematical Programming"},{"key":"264574_CR11","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/BFb0120892","volume":"12","author":"G. Gallo","year":"1980","unstructured":"G. Gallo, P.L. Hammer, and B. Simeone, \u201cQuadratic knapsack problems,\u201d Mathematical Programming Study, vol. 12, pp. 132\u2013149, 1980.","journal-title":"Mathematical Programming Study"},{"key":"264574_CR12","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"M.X. Goemans and D.P. Williamson, \u201cImproved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,\u201d J. ACM, vol. 42, pp. 1115\u20131145, 1995.","journal-title":"J. ACM"},{"key":"264574_CR13","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF01580442","volume":"8","author":"P.L. Hammer","year":"1975","unstructured":"P.L. Hammer, E.L. Johnson, and U.N. Peled, \u201cFacets of regular 0\u20131 polytopes,\u201d Mathematical Programming, vol. 8, pp. 179\u2013206, 1975.","journal-title":"Mathematical Programming"},{"issue":"3","key":"264574_CR14","first-page":"170","volume":"35","author":"P.L. Hammer","year":"1997","unstructured":"P.L. Hammer and D.J. Rader, \u201cEfficient methods for solving quadratic knapsack problems,\u201d INFOR, vol. 35, no. 3, pp. 170\u2013182, 1997.","journal-title":"INFOR"},{"key":"264574_CR15","doi-asserted-by":"crossref","unstructured":"C. Helmberg, S. Poljak, F. Rendl, and H. Wolkowicz, \u201cCombining semidefinite and polyhedral relaxations for integer programs,\u201d in Integer Programming and Combinatorial Optimization, E. Balas and J. Clausen (Eds.), Lecture Notes in Computer Science, vol. 920. Springer, 1995, pp. 124\u2013134.","DOI":"10.1007\/3-540-59408-6_46"},{"key":"264574_CR16","first-page":"291","volume":"82","author":"C. Helmberg","year":"1998","unstructured":"C. Helmberg and F. Rendl, \u201cSolving quadratic (0,1)-problems by semidefinite programs and cutting planes,\u201d Mathematical Programming, vol. 82, pp. 291\u2013315, 1998.","journal-title":"Mathematical Programming"},{"issue":"3","key":"264574_CR17","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C. Helmberg","year":"1997","unstructured":"C. Helmberg and F. Rendl, \u201cA spectral bundle method for semidefinite programming,\u201d Preprint SC-97\u201337, ZIB Berlin, August 1997. Revised October 1997. SIAM J. Optim., vol. 10, no. 3, pp. 673\u2013696.","journal-title":"SIAM J. Optim."},{"key":"264574_CR18","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1137\/0806020","volume":"6","author":"C. Helmberg","year":"1996","unstructured":"C. Helmberg, F. Rendl, R.J. Vanderbei, and H. Wolkowicz, \u201cAn interior-point method for semidefinite programming,\u201d SIAM Journal on Optimization, vol. 6, pp. 342\u2013361, 1996a.","journal-title":"SIAM Journal on Optimization"},{"key":"264574_CR19","doi-asserted-by":"crossref","unstructured":"C. Helmberg, F. Rendl, and R. Weismantel, \u201cQuadratic knapsack relaxations using cutting planes and semidefinite programming, in Integer Programming and Combinatorial Optimization, W.H. Cunningham, S.T. McCormick, and M. Queyranne (Eds.), Springer, June 1996b, pp. 175\u2013189, vol. 1084, Lecture Notes in Computer Science,.","DOI":"10.1007\/3-540-61310-2_14"},{"key":"264574_CR20","doi-asserted-by":"crossref","unstructured":"C. Helmberg and R. Weismantel, \u201cCutting plane algorithms for semidefinite relaxations,\u201d in Pardalos and Wolkowicz (1998), pp. 197\u2013213.","DOI":"10.1090\/fic\/018\/14"},{"key":"264574_CR21","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01585164","volume":"62","author":"E. Johnson","year":"1993","unstructured":"E. Johnson, A. Mehrotra, and G.L. Nemhauser, \u201cMin-cut clustering,\u201d Mathematical Programming, vol. 62, pp. 133\u2013152, 1993.","journal-title":"Mathematical Programming"},{"key":"264574_CR22","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1287\/opre.18.3.454","volume":"18","author":"D.J. Laughhunn","year":"1970","unstructured":"D.J. Laughhunn, \u201cQuadratic binary programming with application to capital-budgeting problems,\u201d Operations Research, vol. 18, pp. 454\u2013461, 1970.","journal-title":"Operations Research"},{"key":"264574_CR23","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/S0167-5060(08)70822-7","volume":"4","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, \u201cGraph theory and integer programming,\u201d Annals of Discrete Mathematics, vol. 4, pp. 141\u2013158, 1979.","journal-title":"Annals of Discrete Mathematics"},{"issue":"2","key":"264574_CR24","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"L. Lov\u00e1sz and A. Schrijver, \u201cCones of matrices and set functions and 0\u20131 optimization,\u201d SIAM J. Optimization, vol. 1, no. 2, pp. 166\u2013190, 1991.","journal-title":"SIAM J. Optimization"},{"key":"264574_CR25","doi-asserted-by":"crossref","unstructured":"J. Mitchell, P.M. Pardalos, and M.G.C. Resende, \u201cInterior point methods for combinatorial optimization,\u201d in Handbook of Combinatorial Optimization, vol. 1, D.-Z. Du and P.M. Pardalos (Eds.), Kluwer, 1998, pp. 189\u2013298.","DOI":"10.1007\/978-1-4613-0303-9_4"},{"key":"264574_CR26","unstructured":"S. N\u00e4her and C. Uhrig, \u201cThe LEDA User Manual Version R 3.3 beta,\u201d Max-Planck-Institut f\u00fcr Informatik, Im Stadtwald, Building 46.1, D-66123 Saarbr\u00fccken, Germany. (http:\/\/www.mpi-sb.mpg.de\/LEDA\/leda.html)"},{"key":"264574_CR27","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1080\/10556789808805690","volume":"9","author":"Y. Nesterov","year":"1998","unstructured":"Y. Nesterov, \u201cSemidefinite relaxation and nonconvex quadratic optimization,\u201d Optimization Methods and Software, vol. 9, pp. 141\u2013160, 1998.","journal-title":"Optimization Methods and Software"},{"key":"264574_CR28","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/BF01589101","volume":"45","author":"M.W. Padberg","year":"1989","unstructured":"M.W. Padberg, \u201cThe boolean quadric polytope,\u201d Mathematical Programming, vol. 45, pp. 132\u2013172, 1989.","journal-title":"Mathematical Programming"},{"key":"264574_CR29","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0024-3795(91)90267-Z","volume":"152","author":"P.M. Pardalos","year":"1991","unstructured":"P.M. Pardalos, Y. Ye, and C.-G. Han, \u201cAlgorithms for the solution of quadratic knapsack problems,\u201d Linear Algebra and its Applications, vol. 152, pp. 69\u201391, 1991.","journal-title":"Linear Algebra and its Applications"},{"key":"264574_CR30","doi-asserted-by":"crossref","unstructured":"P.M. Pardalos and H. Wolkowicz, \u201cTopics in semidefinite and interior-point methods,\u201d Fields Institute Communications, Vol. 18, American Mathematical Society, 1998.","DOI":"10.1090\/fic\/018"},{"issue":"3","key":"264574_CR31","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H. Sherali","year":"1990","unstructured":"H. Sherali and W. Adams, \u201cA hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems,\u201d SIAM J. Discr. Math., vol. 3, no. 3, pp. 411\u2013430, 1990.","journal-title":"SIAM J. Discr. Math."},{"key":"264574_CR32","first-page":"49","volume":"77","author":"R. Weismantel","year":"1997","unstructured":"R. Weismantel, \u201cOn the 0\/1 knapsack polytope,\u201d Mathematical Programming, vol. 77, pp. 49\u201368, 1997.","journal-title":"Mathematical Programming"},{"key":"264574_CR33","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/BF01580441","volume":"8","author":"L.A. Wolsey","year":"1975","unstructured":"L.A. Wolsey, \u201cFaces of linear inequalities in 0\u20131 variables,\u201d Mathematical Programming, vol. 8, pp. 165\u2013178, 1975.","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:1009898604624.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009898604624\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009898604624.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:04:51Z","timestamp":1751281491000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009898604624"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,6]]}},"alternative-id":["264574"],"URL":"https:\/\/doi.org\/10.1023\/a:1009898604624","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,6]]}}}