{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:47:54Z","timestamp":1774946874062,"version":"3.50.1"},"reference-count":56,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2002,6,1]],"date-time":"2002-06-01T00:00:00Z","timestamp":1022889600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4064,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2002,6]]},"DOI":"10.1016\/s0166-218x(01)00266-9","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T11:32:09Z","timestamp":1027596729000},"page":"79-106","source":"Crossref","is-referenced-by-count":36,"title":["Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem"],"prefix":"10.1016","volume":"119","author":[{"given":"Miguel F.","family":"Anjos","sequence":"first","affiliation":[]},{"given":"Henry","family":"Wolkowicz","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(01)00266-9_BIB1","unstructured":"F. Alizadeh, J.-P. Haeberly, M.V. Nayakkankuppam, M.L. Overton, S. Schmieta, SDP pack user's guide\u2014version 0.9 Beta, Technical Report TR1997-737, Courant Institute of Mathematical Sciences, NYU, New York, NY, June 1997."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB2","unstructured":"M.F. Anjos, H. Wolkowicz, A strengthened SDP relaxation via a second lifting for the Max-Cut problem, Technical Research Report, CORR 99-55, University of Waterloo, Waterloo, Ont., 1999, 28p."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB3","unstructured":"M.F. Anjos, H. Wolkowicz, A tight semidefinite relaxation of the cut polytope, Technical Research Report, CORR 2000-19, University of Waterloo, Waterloo, Ont., 2000, 24p."},{"issue":"1\u20133","key":"10.1016\/S0166-218X(01)00266-9_BIB4","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0024-3795(99)00205-0","article-title":"Strong duality for a trust-region type relaxation of the quadratic assignment problems","volume":"301","author":"Anstreicher","year":"1999","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"10.1016\/S0166-218X(01)00266-9_BIB5","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/S0895479898340299","article-title":"On Lagrangian relaxation of quadratic matrix constraints","volume":"22","author":"Anstreicher","year":"2000","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB6","doi-asserted-by":"crossref","unstructured":"E. Balas, A modified lift-and-project procedure, Math. Programming Ser. B 79(1\u20133) 19\u201331, 1997, Lectures on Mathematical Programming, ismp97, Lausanne, 1997.","DOI":"10.1007\/BF02614309"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB7","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01581273","article-title":"A lift-and-project cutting plane algorithm for mixed 0-1 programs","volume":"58","author":"Balas","year":"1993","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB8","unstructured":"E. Balas, S. Ceria, G. Cornu\u00e9jols, Solving mixed 0-1 programs by a lift-and-project method, in: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, 1993, ACM, New York, 1993, pp. 232\u2013242."},{"issue":"3","key":"10.1016\/S0166-218X(01)00266-9_BIB9","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0167-6377(83)90016-0","article-title":"The max-cut problem on graphs not contractible to K5","volume":"2","author":"Barahona","year":"1983","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"10.1016\/S0166-218X(01)00266-9_BIB10","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01580600","article-title":"On cuts and matchings in planar graphs","volume":"60","author":"Barahona","year":"1993","journal-title":"Math. Programming Ser. A"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB11","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","article-title":"An application of combinatorial optimization to statistical physics and circuit layout design","volume":"36","author":"Barahona","year":"1988","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB12","doi-asserted-by":"crossref","unstructured":"S.J. Benson, Y. Ye, X. Zhang, Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM J. Optim. 10(2) (2000) 443\u2013461 (electronic).","DOI":"10.1137\/S1052623497328008"},{"issue":"1\u20134","key":"10.1016\/S0166-218X(01)00266-9_BIB13","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1080\/10556789908805765","article-title":"CSDP, a C library for semidefinite programming","volume":"11\/12","author":"Borchers","year":"1999","journal-title":"Optim. Methods Software (Interior point methods)"},{"issue":"1","key":"10.1016\/S0166-218X(01)00266-9_BIB14","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1080\/10556789908805769","article-title":"SDPLIB 1.2, a library of semidefinite programming test problems","volume":"11","author":"Borchers","year":"1999","journal-title":"Optim. Methods Software (Interior point methods)"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB15","unstructured":"S. Burer, R.D.C. Monteiro, An efficient algorithm for solving the MAXCUT SDP relaxation, Technical Report, Georgia Tech., Atlanta, GA, 1999."},{"issue":"3","key":"10.1016\/S0166-218X(01)00266-9_BIB16","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","article-title":"Laplacian eigenvalues and the maximum cut problem","volume":"62","author":"Delorme","year":"1993","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB17","series-title":"Geometry of Cuts and Metrics","author":"Deza","year":"1997"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB18","unstructured":"U. Feige, G. Schechtman, On the optimality of the random hyperplane rounding technique for MAX CUT, Technical Report, Weizmann Institute, Rehovot, Israel, 2000."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB19","series-title":"Computers and Intractabilty: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB20","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF02614315","article-title":"Semidefinite programming in combinatorial optimization","volume":"79","author":"Goemans","year":"1997","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB21","doi-asserted-by":"crossref","unstructured":"M.X. Goemans, Semidefinite programming and combinatorial optimization, Documenta Math. ICM 1998 (1998) 657\u2013666 (Invited talk at the International Congress of Mathematicians, Berlin, 1998).","DOI":"10.4171\/dms\/1-3\/63"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB22","series-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","article-title":"Combinatorial optimization","author":"Goemans","year":"2000"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB23","doi-asserted-by":"crossref","unstructured":"M.X. Goemans, D.P. Williamson, .878-approximation algorithms for MAX CUT and MAX 2SAT, in: ACM Symposium on Theory of Computing (STOC), Montr\u00e9al, Qu\u00e9bec, 1994.","DOI":"10.1145\/195058.195216"},{"issue":"6","key":"10.1016\/S0166-218X(01)00266-9_BIB24","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB25","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","article-title":"Positive definite completions of partial Hermitian matrices","volume":"58","author":"Grone","year":"1984","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB26","doi-asserted-by":"crossref","unstructured":"J. Hastad, Some optimal inapproximability results, in: Proceedings of the 29th ACM Symposium on Theory and Computation, 1997.","DOI":"10.1145\/258533.258536"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB27","unstructured":"C. Helmberg, An interior-point method for semidefinite programming and max-cut bounds, PhD Thesis, Graz University of Technology, Austria, 1994."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB28","unstructured":"C. Helmberg, SBmethod\u2014A C++ implementation of the spectral bundle method, ZIB preprint 00-35, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin, Takustra\u00dfe 7, 14196, Berlin, Germany, October 2000."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB29","unstructured":"C. Helmberg, K.C. Kiwiel, A spectral bundle method with bounds, ZIP preprint sc-99-37, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin, Takustra\u00dfe 7, 14195, Berlin, Germany, November 1999."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB30","series-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","article-title":"Bundle methods to minimize the maximum eigenvalue function","author":"Helmberg","year":"2000"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB31","doi-asserted-by":"crossref","unstructured":"C. Helmberg, S. Poljak, F, Rendl, H. Wolkowicz, Combining semidefinite and polyhedral relaxations for integer programs, in: Integer Programming and Combinatorial Optimization (Copenhagen, 1995), Springer, Berlin, 1995, pp. 124\u2013134.","DOI":"10.1007\/3-540-59408-6_46"},{"issue":"3","key":"10.1016\/S0166-218X(01)00266-9_BIB32","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","article-title":"A spectral bundle method for semidefinite programming","volume":"10","author":"Helmberg","year":"2000","journal-title":"SIAM J. Optim."},{"issue":"2","key":"10.1016\/S0166-218X(01)00266-9_BIB33","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1137\/0806020","article-title":"An interior-point method for semidefinite programming","volume":"6","author":"Helmberg","year":"1996","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB34","unstructured":"R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1994 (corrected reprint of the 1991 original)."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB35","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1090\/psapm\/040\/1059486","article-title":"Matrix completion problems: a survey","volume":"40","author":"Johnson","year":"1990","journal-title":"Proc. Symp. Appl. Math."},{"issue":"2","key":"10.1016\/S0166-218X(01)00266-9_BIB36","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1023\/A:1018363021404","article-title":"An interior-point method for approximate positive semidefinite completions","volume":"9","author":"Johnson","year":"1998","journal-title":"Comput. Optim. Appl."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB37","series-title":"Complexity of Computer Computation","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB38","doi-asserted-by":"crossref","unstructured":"J.B. Lasserre, Optimality conditions and LMI relaxations for 0-1 programs, LAAS Research Report, LAAS-CNRS, Toulouse, France, 2000.","DOI":"10.1109\/CDC.2001.914738"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB39","doi-asserted-by":"crossref","unstructured":"M. Laurent, A tour d'horizon on positive semidefinite and Euclidean distance matrix completion problems, in: Topics in Semidefinite and Interior-Point Methods, The Fields Institute for Research in Mathematical Sciences, Communications Series, Vol. 18, American Mathematical Society, Providence, RI, 1998, pp. 51\u201376.","DOI":"10.1090\/fic\/018\/05"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB40","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/0024-3795(95)00271-R","article-title":"On a positive semidefinite relaxation of the cut polytope","volume":"223\/224","author":"Laurent","year":"1995","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"10.1016\/S0166-218X(01)00266-9_BIB41","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1137\/0617031","article-title":"On the facial structure of the correlation matrices","volume":"17","author":"Laurent","year":"1996","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB42","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF02614436","article-title":"Connections between semidefinite relaxations of the max-cut and stable set problems","volume":"77","author":"Laurent","year":"1997","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB43","doi-asserted-by":"crossref","unstructured":"T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Wiley, Chichester, 1990 (with a foreword by Bryan Preas).","DOI":"10.1007\/978-3-322-92106-2_3"},{"issue":"2","key":"10.1016\/S0166-218X(01)00266-9_BIB44","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","article-title":"Cones of matrices and set-functions and 0-1 optimization","volume":"1","author":"Lov\u00e1sz","year":"1991","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB45","doi-asserted-by":"crossref","unstructured":"B. Mohar, S. Poljak, Eigenvalues in combinatorial optimization, in: Combinatorial Graph-Theoretical Problems in Linear algebra, IMA, Vol. 50, Springer, Berlin, 1993.","DOI":"10.1007\/978-1-4613-8354-3_5"},{"key":"10.1016\/S0166-218X(01)00266-9_BIB46","unstructured":"Y.E. Nesterov, Quality of semidefinite relaxation for nonconvex quadratic optimization, Technical Report, CORE, Universite Catholique de Louvain, Belgium, 1997."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB47","series-title":"Handbook of Semidefinite Programming: Theory, Algorithms and Applications","first-page":"34","article-title":"Semidefinite programming relaxations of nonconvex quadratic optimization","author":"Nesterov","year":"2000"},{"issue":"1","key":"10.1016\/S0166-218X(01)00266-9_BIB48","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01100205","article-title":"A recipe for semidefinite relaxation for (0,1)-quadratic programming","volume":"7","author":"Poljak","year":"1995","journal-title":"J. Global Optim."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB49","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0168-9274(98)00097-X","article-title":"Semidefinite programming and combinatorial optimization","volume":"29","author":"Rendl","year":"1999","journal-title":"Appl. Numer. Math."},{"issue":"3","key":"10.1016\/S0166-218X(01)00266-9_BIB50","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","article-title":"A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems","volume":"3","author":"Sherali","year":"1990","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"10.1016\/S0166-218X(01)00266-9_BIB51","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0166-218X(92)00190-W","article-title":"A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems","volume":"52","author":"Sherali","year":"1994","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"10.1016\/S0166-218X(01)00266-9_BIB52","first-page":"128","article-title":"Quadratic optimization problems","volume":"222","author":"Shor","year":"1987","journal-title":"Izv. Akad. Nauk SSSR Tekhn. Kibernet."},{"issue":"2","key":"10.1016\/S0166-218X(01)00266-9_BIB53","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1137\/0805016","article-title":"Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations","volume":"5","author":"Stern","year":"1995","journal-title":"SIAM J. Optim."},{"issue":"1","key":"10.1016\/S0166-218X(01)00266-9_BIB54","first-page":"81","article-title":"The S-procedure and duality theorems for non-convex problems of quadratic programming","volume":"1973","author":"Yakubovich","year":"1973","journal-title":"Vestnik Leningrad Univ."},{"issue":"1","key":"10.1016\/S0166-218X(01)00266-9_BIB55","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0167-6911(92)90034-P","article-title":"Nonconvex optimization problem: the infinite-horizon linear-quadratic control problem with quadratic constraints","volume":"19","author":"Yakubovich","year":"1992","journal-title":"Systems Control Lett."},{"key":"10.1016\/S0166-218X(01)00266-9_BIB56","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s10107980012a","article-title":"Approximating quadratic programming with bound and quadratic constraints","volume":"84","author":"Ye","year":"1999","journal-title":"Math. Programming"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X01002669?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X01002669?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T06:56:14Z","timestamp":1680850574000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X01002669"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,6]]},"references-count":56,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2002,6]]}},"alternative-id":["S0166218X01002669"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(01)00266-9","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2002,6]]}}}