{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T04:07:06Z","timestamp":1751342826051,"version":"3.41.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2002,9,1]],"date-time":"2002-09-01T00:00:00Z","timestamp":1030838400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,9,1]],"date-time":"2002-09-01T00:00:00Z","timestamp":1030838400000},"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":[[2002,9]]},"DOI":"10.1023\/a:1014895808844","type":"journal-article","created":{"date-parts":[[2002,12,28]],"date-time":"2002-12-28T21:20:03Z","timestamp":1041110403000},"page":"237-270","source":"Crossref","is-referenced-by-count":8,"title":["Geometry of Semidefinite Max-Cut Relaxations via Matrix Ranks"],"prefix":"10.1007","volume":"6","author":[{"given":"Miguel F.","family":"Anjos","sequence":"first","affiliation":[]},{"given":"Henry","family":"Wolkowicz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"401842_CR1","unstructured":"M.F. Anjos, \u201cNew convex relaxations for the Maximum Cut and VLSI layout problems,\u201d Ph.D. Thesis, University of Waterloo, 2001. Available online at http:\/\/etd.uwaterloo.ca\/etd\/manjos2001.pdf."},{"issue":"1-2","key":"401842_CR2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0166-218X(01)00266-9","volume":"199","author":"M.F. Anjos","year":"2002","unstructured":"M.F. Anjos and H. Wolkowicz, \u201cStrengthened semidefinite relaxations via a second lifting for the Max-Cut problem,\u201d Discrete Appl. Math., vol. 199, no. 1-2, pp. 79\u2013106, 2002.","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"401842_CR3","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0167-6377(83)90016-0","volume":"2","author":"F. Barahona","year":"1983","unstructured":"F. Barahona, \u201cThe max-cut problem on graphs not contractible to K5,\u201d Oper. Res. Lett., vol. 2, no. 3, pp. 107\u2013111, 1983.","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"401842_CR4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01580600","volume":"60","author":"F. Barahona","year":"1993","unstructured":"F. Barahona, \u201cOn cuts and matchings in planar graphs,\u201d Math. Programming, vol. 60, no. 1 (Ser. A), pp. 53\u201368, 1993.","journal-title":"Math. Programming"},{"key":"401842_CR5","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F. Barahona","year":"1988","unstructured":"F. Barahona, M. Gr\u00f6tschel, M. J\u00a8unger, and G. Reinelt, \u201cAn application of combinatorial optimization to statistical physics and circuit layout design,\u201d Oper. Res., vol. 36, pp. 493\u2013513, 1988.","journal-title":"Oper. Res."},{"issue":"2","key":"401842_CR6","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"F. Barahona and A.R. Mahjoub, \u201cOn the cut polytope,\u201d Math. Programming, vol. 36, no. 2, pp. 157\u2013173, 1986.","journal-title":"Math. Programming"},{"issue":"2","key":"401842_CR7","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1137\/S1052623497328008","volume":"10","author":"S.J. Benson","year":"2000","unstructured":"S.J. Benson, Y. Ye, and X. Zhang, \u201cSolving large-scale sparse semidefinite programs for combinatorial optimization,\u201d SIAM J. Optim., vol. 10, no. 2, pp. 443\u2013461 (electronic), 2000.","journal-title":"SIAM J. Optim."},{"key":"401842_CR8","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1080\/10556780108805818","volume":"15","author":"S. Burer","year":"2001","unstructured":"S. Burer and R.D.C. Monteiro, \u201cA projected gradient algorithm for solving the maxcut SDP relaxation,\u201d Optim. Meth. Softw., vol. 15, pp. 175\u2013200, 2001.","journal-title":"Optim. Meth. Softw."},{"key":"401842_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of Cuts and Metrics","author":"M.M. Deza","year":"1997","unstructured":"M.M. Deza and M. Laurent, Geometry of Cuts and Metrics, Springer-Verlag: Berlin, 1997."},{"key":"401842_CR10","volume-title":"Technical report","author":"U. Feige","year":"2000","unstructured":"U. Feige and G. Schechtman, \u201cOn the optimality of the random hyper plane rounding technique for MAX CUT,\u201d Technical report, Weizmann Institute, Rehovot, Israel, 2000."},{"key":"401842_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman: San Francisco, 1979."},{"key":"401842_CR12","first-page":"143","volume":"79","author":"M.X. Goemans","year":"1997","unstructured":"M.X. Goemans, \u201cSemi definite programming in combinatorial optimization,\u201d Math. Programming, vol. 79, pp. 143\u2013162, 1997.","journal-title":"Math. Programming"},{"key":"401842_CR13","doi-asserted-by":"crossref","unstructured":"M.X. Goemans, \u201cSemi definite programming and combinatorial optimization,\u201d Documenta Mathematica, Extra Volume ICM 1998, pp. 657\u2013666, 1998.","DOI":"10.4171\/dms\/1-3\/63"},{"key":"401842_CR14","volume-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","author":"M.X. Goemans","year":"2000","unstructured":"M.X. Goemans and F. Rendl, \u201cCombinatorial optimization,\u201d in Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, H. Wolkowicz, R. Saigal, and L. Vandenberghe (Eds.), Kluwer Academic Publishers: Boston, MA, 2000."},{"key":"401842_CR15","doi-asserted-by":"crossref","unstructured":"M.X. Goemans and D.P. Williamson, \u201c.878-approximation algorithms for MAX CUT and MAX 2SAT,\u201d in ACM Symposium on Theory of Computing (STOC), 1994.","DOI":"10.1145\/195058.195216"},{"issue":"6","key":"401842_CR16","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 semi definite programming,\u201d J. Assoc. Comput. Mach., vol. 42, no. 6, pp. 1115\u20131145, 1995.","journal-title":"J. Assoc. Comput. Mach."},{"key":"401842_CR17","unstructured":"J. Hastad, \u201cSome optimal in approximability results,\u201d in Proc. of the 29th ACM Symp. on Theory Comput., 1997."},{"key":"401842_CR18","volume-title":"An interior-point method for semi definite programming and max-cut bounds","author":"C. Helmberg","year":"1994","unstructured":"C. Helmberg, \u201cAn interior-point method for semi definite programming and max-cut bounds,\u201d PhD Thesis, Graz University of Technology, Austria, 1994."},{"key":"401842_CR19","volume-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","author":"C. Helmberg","year":"2000","unstructured":"C. Helmberg and F. Oustry, \u201cBundle methods to minimize the maximum eigenvalue function,\u201d in Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, H. Wolkowicz, R. Saigal, and L. Vandenberghe (Eds.), Kluwer Academic Publishers: Boston, MA, 2000."},{"key":"401842_CR20","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/3-540-59408-6_46","volume-title":"Integer Programming and Combinatorial Optimization","author":"C. Helmberg","year":"1995","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 (Copenhagen, 1995), Springer: Berlin, 1995, pp. 124\u2013134."},{"issue":"3","key":"401842_CR21","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C. Helmberg","year":"2000","unstructured":"C. Helmberg and F. Rendl, \u201cA spectral bundle method for semi definite programming,\u201d SIAM J. Optim., vol. 10, no. 3, pp. 673\u2013696, 2000.","journal-title":"SIAM J. Optim."},{"issue":"2","key":"401842_CR22","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 semi definite programming,\u201d SIAM J. Optim., vol. 6, no. 2, pp. 342\u2013361, 1996.","journal-title":"SIAM J. Optim."},{"key":"401842_CR23","volume-title":"Matrix Analysis","author":"R.A. Horn","year":"1990","unstructured":"R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press: Cambridge, 1990."},{"key":"401842_CR24","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computation","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, \u201cReducibility among combinatorial problems,\u201d in Complexity of Computer Computation, R.E. Miller and J.W. Thatcher (Eds.), Plenum Press: New York, 1972, pp. 85\u2013103."},{"key":"401842_CR25","series-title":"LAAS research report","volume-title":"Optimality conditions and LMI relaxations for 0-1 programs","author":"J.B. Lasserre","year":"2000","unstructured":"J.B. Lasserre, \u201cOptimality conditions and LMI relaxations for 0-1 programs,\u201d LAAS research report 00099, LAAS-CNRS, Toulouse, France, 2000."},{"key":"401842_CR26","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/S1052623400379371","volume":"12","author":"M. Laurent","year":"2001","unstructured":"M. Laurent, \u201cTighter linear and semi definite relaxations for max-cut based on the Lov\u00e1sz-Schrijver lift-and-project procedure,\u201d SIAM J. Optim., vol. 12, pp. 345\u2013375, 2001 (electronic publication).","journal-title":"SIAM J. Optim."},{"key":"401842_CR27","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/0024-3795(95)00271-R","volume":"223","author":"M. Laurent","year":"1995","unstructured":"M. Laurent and S. Poljak, \u201cOn a positive semi definite relaxation of the cut polytope,\u201d Linear Algebra Appl., vol. 223\/224, pp. 439\u2013461, 1995.","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"401842_CR28","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1137\/0617031","volume":"17","author":"M. Laurent","year":"1996","unstructured":"M. Laurent and S. Poljak, \u201cOn the facial structure of the correlation matrices,\u201d SIAM J. Matrix Anal. Appl., vol. 17, no. 3, pp. 530\u2013547, 1996.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"401842_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"T. Lengauer","year":"1990","unstructured":"T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, JohnWiley & Sons Ltd.: Chichester, 1990."},{"key":"401842_CR30","volume-title":"Combinatorial Graph-Theoretical Problems in Linear Algebra","author":"B. Mohar","year":"1993","unstructured":"B. Mohar and S. Poljak, \u201cEigenvalues in combinatorial optimization,\u201d in Combinatorial Graph-Theoretical Problems in Linear Algebra, IMA, vol. 50, Springer-Verlag: Berlin, 1993."},{"key":"401842_CR31","volume-title":"Technical report","author":"Y.E. Nesterov","year":"1997","unstructured":"Y.E. Nesterov, \u201cQuality of semidefinite relaxation for non convex quadratic optimization,\u201d Technical report, CORE, Universite Catholique de Louvain, Belgium, 1997."},{"key":"401842_CR32","first-page":"34","volume-title":"Handbook of Semi definite Programming: Theory, Algorithms, and Applications","author":"Y.E. Nesterov","year":"2000","unstructured":"Y.E. Nesterov, H. Wolkowicz, and Y. Ye, \u201cSemi definite programming relaxations of nonconvex quadratic optimization,\u201d in Handbook of Semi definite Programming: Theory, Algorithms, and Applications, H. Wolkowicz, R. Saigal, and L. Vandenberghe (Eds.), Kluwer Academic Publishers: Boston, MA, 2000, p. 34."},{"key":"401842_CR33","volume-title":"Structured semi definite programs and semi algebraic geometry methods in robustness and optimization","author":"P. Parrilo","year":"2000","unstructured":"P. Parrilo, \u201cStructured semi definite programs and semi algebraic geometry methods in robustness and optimization,\u201d Ph.D. Thesis, Caltech, Pasadena, California, 2000."},{"key":"401842_CR34","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0168-9274(98)00097-X","volume":"29","author":"F. Rendl","year":"1999","unstructured":"F. Rendl, \u201cSemi definite programming and combinatorial optimization,\u201d Appl. Numer. Math., vol. 29, pp. 255\u2013281, 1999.","journal-title":"Appl. Numer. Math."},{"key":"401842_CR35","first-page":"xxvi+654","volume-title":"Handbook of Semi definite Programming: Theory, Algorithms, and Applications","year":"2000","unstructured":"H. Wolkowicz, R. Saigal, and L. Vandenberghe (Eds.), Handbook of Semi definite Programming: Theory, Algorithms, and Applications, Kluwer Academic Publishers: Boston, MA, 2000, pp. xxvi+654."},{"key":"401842_CR36","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s10107980012a","volume":"84","author":"Y. Ye","year":"1999","unstructured":"Y. Ye, \u201cApproximating quadratic programming with bound and quadratic constraints,\u201d Math. Programming, vol. 84, pp. 219\u2013226, 1999.","journal-title":"Math. Programming"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1014895808844.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1014895808844\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1014895808844.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:05:56Z","timestamp":1751281556000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1014895808844"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,9]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2002,9]]}},"alternative-id":["401842"],"URL":"https:\/\/doi.org\/10.1023\/a:1014895808844","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2002,9]]}}}