{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T21:40:22Z","timestamp":1768081222349,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"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":[[1997,4]]},"DOI":"10.1007\/bf02614436","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T00:40:49Z","timestamp":1177720849000},"page":"225-246","source":"Crossref","is-referenced-by-count":10,"title":["Connections between semidefinite relaxations of the max-cut and stable set problems"],"prefix":"10.1007","volume":"77","author":[{"given":"Monique","family":"Laurent","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Svatopluk","family":"Poljak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franz","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02614436_CR1","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, A lift-and-project cutting plane algorithm for mixed 0\u20131 programs,Mathematical Programming 58 (1993) 295\u2013324.","journal-title":"Mathematical Programming"},{"key":"BF02614436_CR2","series-title":"Technical Report","doi-asserted-by":"crossref","DOI":"10.21236\/ADA298925","volume-title":"Polyhedral methods for the maximum clique problem","author":"E. Balas","year":"1994","unstructured":"E. Balas, S. Ceria, G. Cornuejols and G. Pataki, Polyhedral methods for the maximum clique problem, Technical Report, Carnegie Mellon University, Pittsburgh, PA, 1994."},{"key":"BF02614436_CR3","series-title":"Technical Report","volume-title":"Updated semi-definite constraints","author":"E. Balas","year":"1994","unstructured":"E. Balas, S. Ceria, G. Cornuejols and G. Pataki, Updated semi-definite constraints, Technical Report, Carnegie Mellon University, Pittsburgh, PA, 1994."},{"key":"BF02614436_CR4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01580600","volume":"60","author":"F. Barahona","year":"1993","unstructured":"F. Barahona, On cuts and matchings in planar graphs,Mathematical Programming 60 (1993) 53\u201368.","journal-title":"Mathematical Programming"},{"key":"BF02614436_CR5","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, On the cut polytope,Mathematical Programming 36 (1986) 157\u2013173.","journal-title":"Mathematical Programming"},{"key":"BF02614436_CR6","doi-asserted-by":"crossref","unstructured":"W.W. Barrett, C.R. Johnson and R. Loewy, The real positive definite completion problem: Cycle completability,Memoirs of the AMS 584 (1996).","DOI":"10.1090\/memo\/0584"},{"key":"BF02614436_CR7","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","volume":"63","author":"C. Delorme","year":"1993","unstructured":"C. Delorme and S. Poljak, Laplacian eigenvalues and the max-cut problem,Mathematical Programming 63 (1993) 557\u2013574.","journal-title":"Mathematical Programming"},{"key":"BF02614436_CR8","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0012-365X(90)90056-N","volume":"79","author":"C. Simone De","year":"1989","unstructured":"C. De Simone, The cut polytope and the boolean quadric polytope,Discrete Mathematics 79 (1989\/1990) 71\u201375.","journal-title":"Discrete Mathematics"},{"key":"BF02614436_CR9","doi-asserted-by":"crossref","unstructured":"U. Feige and M.X. Goemans, Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT, in:Proceedings of the Israel Symposium on Theory of Computing and Systems, 1995, 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"BF02614436_CR10","unstructured":"A.M.H. Gerards and F.B. Shepherd, The characterization of graphs with all subgraphst-perfect, Research Report LSE-CDAM-96-09, Centre for Discrete and Applicable Mathematics, London School of Economics and Political Science, June 1996."},{"key":"BF02614436_CR11","unstructured":"M.X. Goemans and D.P. Williamson, .878-approximation algorithms for MAX CUT and MAX 2SAT, in:Proceedings of the 26th Annual Symposium on Theory of Computing, Montr\u00e9al (1994) 422\u2013431."},{"key":"BF02614436_CR12","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"R. Grone","year":"1984","unstructured":"R. Grone, C.R. Johnson, E.M. S\u00e1 and H. Wolkowicz, Positive definite completions of partial hermitian matrices,Linear Algebra and its Applications 58 (1984) 109\u2013124.","journal-title":"Linear Algebra and its Applications"},{"key":"BF02614436_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988)."},{"key":"BF02614436_CR14","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/opre.13.3.388","volume":"13","author":"P.L. Hammer","year":"1965","unstructured":"P.L. Hammer, Some network flow problems solved with pseudo-boolean programming,Operations Research 13 (1965) 388\u2013399.","journal-title":"Operations Research"},{"key":"BF02614436_CR15","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF02612354","volume":"28","author":"P.L. Hammer","year":"1984","unstructured":"P.L. Hammer, P. Hansen and B. Simeone, Roof duality, complementation and persistency in quadratic 0\u20131 optimization,Mathematical Programming 28 (1984) 121\u2013155.","journal-title":"Mathematical Programming"},{"key":"BF02614436_CR16","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, A primal-dual interior point method for the max-min eigenvalue problem,SIAM Journal on Optimization 6 (1996) 342\u2013361.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614436_CR17","doi-asserted-by":"crossref","unstructured":"J. Kleinberg and M. Goemans, The Lov\u00e1sz theta function and a semidefinite programming relaxation of vertex cover,SIAM Journal on Discrete Mathematics, to appear.","DOI":"10.1137\/S0895480195287541"},{"key":"BF02614436_CR18","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0024-3795(95)00741-5","volume":"252","author":"M. Laurent","year":"1997","unstructured":"M. Laurent, The real positive semidefinite completion problem for series-parallel graphs,Linear Algebra and its Applications 252 (1997) 347\u2013366.","journal-title":"Linear Algebra and its Applications"},{"key":"BF02614436_CR19","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/0024-3795(95)00271-R","volume":"223\/224","author":"M. Laurent","year":"1995","unstructured":"M. Laurent and S. Poljak, On a positive semidefinite relaxation of the cut polytope,Linear Algebra and its Applications 223\/224 (1995) 439\u2013461.","journal-title":"Linear Algebra and its Applications"},{"key":"BF02614436_CR20","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1137\/0617031","volume":"17","author":"M. Laurent","year":"1996","unstructured":"M. Laurent and S. Poljak, On the facial structure of the set of correlation matrices,SIAM Journal on Matrix Analysis and Applications 17 (1996) 530\u2013547.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"2","key":"BF02614436_CR21","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, Cones of matrices and set-functions and 0\u20131 optimization,SIAM Journal of Optimization 1 (2) (1991) 166\u2013190.","journal-title":"SIAM Journal of Optimization"},{"key":"BF02614436_CR22","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M. Padberg","year":"1989","unstructured":"M. Padberg, The boolean quadric polytope: Some characteristics, facets and relatives,Mathematical Programming 45 (1989) 139\u2013172.","journal-title":"Mathematical Programming"},{"key":"BF02614436_CR23","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1137\/0805024","volume":"5","author":"S. Poljak","year":"1995","unstructured":"S. Poljak and F. Rendl, Nonpolyhedral relaxation of graph-bisection problems,SIAM Journal on Optimization 5 (1995) 467\u2013487.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614436_CR24","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0167-6377(94)90068-X","volume":"16","author":"S. Poljak","year":"1994","unstructured":"S. Poljak and Zs. Tuza, On the expected relative error of the polyhedral approximation of the max-cut,Operations Research Letters 16 (1994) 191\u2013198.","journal-title":"Operations Research Letters"},{"key":"BF02614436_CR25","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A. Schrijver","year":"1979","unstructured":"A. Schrijver, A comparison of the Delsarte and Lov\u00e1sz bound,IEEE Transactions on Information Theory 25 (1979) 425\u2013429.","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614436.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02614436\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614436","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T04:49:26Z","timestamp":1558327766000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02614436"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["BF02614436"],"URL":"https:\/\/doi.org\/10.1007\/bf02614436","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}