{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T07:50:09Z","timestamp":1771573809920,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,10,28]],"date-time":"2010-10-28T00:00:00Z","timestamp":1288224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s10107-010-0425-z","type":"journal-article","created":{"date-parts":[[2010,10,26]],"date-time":"2010-10-26T23:55:58Z","timestamp":1288137358000},"page":"203-225","source":"Crossref","is-referenced-by-count":13,"title":["A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs"],"prefix":"10.1007","volume":"133","author":[{"given":"Jo\u00e3o","family":"Gouveia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monique","family":"Laurent","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo A.","family":"Parrilo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rekha","family":"Thomas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,10,28]]},"reference":[{"key":"425_CR1","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0167-6377(83)90016-0","volume":"2","author":"F. Barahona","year":"1983","unstructured":"Barahona F.: The max-cut problem on graphs not contractible to K 5. Oper. Res. Lett. 2, 107\u2013111 (1983)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"425_CR2","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/0095-8956(86)90063-8","volume":"40","author":"F. Barahona","year":"1986","unstructured":"Barahona F., Gr\u00f6tschel M.: On the cycle polytope of a binary matroid. J. Combinatorial Theory Ser. B 40(1), 40\u201362 (1986)","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"425_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03718-8","volume-title":"Real Algebraic Geometry","author":"J. Bochnak","year":"1998","unstructured":"Bochnak J., Coste M., Roy M.-F.: Real Algebraic Geometry. Springer, Berlin (1998)"},{"key":"425_CR4","volume-title":"Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra","author":"D.A. Cox","year":"2005","unstructured":"Cox D.A., Little J.B., O\u2019Shea D.B.: Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, Berlin (2005)"},{"key":"425_CR5","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":"Deza M.M., Laurent M.: Geometry of Cuts and Metrics. Springer, Berlin (1997)"},{"key":"425_CR6","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J. Edmonds","year":"1973","unstructured":"Edmonds J., Johnson E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5, 88\u2013124 (1973)","journal-title":"Math. Program."},{"key":"425_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Company, Publishers, San Francisco (1979)"},{"key":"425_CR8","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans M.X., Williamson D.: Improved approximation algorithms for maximum cuts and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"425_CR9","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.: Theta bodies for polynomial ideals, preprint. arXiv:0809.3480 (2008)"},{"key":"425_CR10","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1016\/0024-3795(89)90478-3","volume":"114\/114","author":"M. Gr\u00f6tschel","year":"1989","unstructured":"Gr\u00f6tschel M., Truemper K.: Master polytopes for cycles of binary matroids. Linear Algebra Appl. 114\/114, 523\u2013540 (1989)","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"425_CR11","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/0095-8956(89)90052-X","volume":"46","author":"M. Gr\u00f6tschel","year":"1989","unstructured":"Gr\u00f6tschel M., Truemper K.: Decomposition and optimization over cycles in binary matroids. J. Combinatotorial Theory B 46(3), 306\u2013337 (1989)","journal-title":"J. Combinatotorial Theory B"},{"key":"425_CR12","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0\u20131 programs. In: Aardal, K., Gerards, A.M.H. (eds.) Lecture Notes in Computer Science, vol. 2081, pp. 293\u2013303 (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"issue":"3","key":"425_CR13","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M. Laurent","year":"2003","unstructured":"Laurent M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver and Lasserre relaxations for 0\u20131 programming. Math. Oper. Res. 28(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"425_CR14","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1287\/moor.28.4.871.20508","volume":"28","author":"M. Laurent","year":"2003","unstructured":"Laurent M.: Lower bound for the number of iterations in semidefinite relaxations for the cut polytope. Math. Oper. Res. 28(4), 871\u2013883 (2003)","journal-title":"Math. Oper. Res."},{"key":"425_CR15","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Semidefinite relaxations for max-cut. In: The sharpest cut, MPS\/SIAM Ser. Optim., pp. 257\u2013290. SIAM, Philadelphia, PA (2004)","DOI":"10.1137\/1.9780898718805.ch16"},{"key":"425_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-004-0561-4","volume":"109","author":"M. Laurent","year":"2007","unstructured":"Laurent M.: Semidefinite representations for finite varieties. Math. Program. 109, 1\u201326 (2007)","journal-title":"Math. Program."},{"key":"425_CR17","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/S0927-0507(05)12008-8","volume-title":"Handbook on Discrete Optimization","author":"M. Laurent","year":"2005","unstructured":"Laurent M., Rendl F.: Semidefinite programming and integer programming. In: Aardal, K., Nemhauser, G., Weismantel, R. (eds) Handbook on Discrete Optimization, pp. 393\u2013514. Elsevier B.V., Amsterdam (2005)"},{"key":"425_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"IT-25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT-25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"425_CR19","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Semidefinite programs and combinatorial optimization. In: Recent advances in algorithms and combinatorics, volume 11 of CMS Books Math.\/Ouvrages Math. SMC, pp. 137\u2013194. Springer, New York (2003)","DOI":"10.1007\/0-387-22444-0_6"},{"key":"425_CR20","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz L., Schrijver A.: Cones of matrices and set-functions and 0\u20131 optimization. SIAM J. Optim. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"425_CR21","volume-title":"Matroid Theory","author":"J.G. Oxley","year":"1992","unstructured":"Oxley J.G.: Matroid Theory. Oxford University Press, Oxford (1992)"},{"key":"425_CR22","doi-asserted-by":"crossref","unstructured":"Parrilo P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Prog. 96(2, Ser. B), 293\u2013320 (2003)","DOI":"10.1007\/s10107-003-0387-5"},{"key":"425_CR23","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. Sherali","year":"1990","unstructured":"Sherali H.D., Adams W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discr. Math. 3, 411\u2013430 (1990)","journal-title":"SIAM J. Discr. Math."},{"issue":"3","key":"425_CR24","doi-asserted-by":"publisher","first-page":"433","DOI":"10.2748\/tmj\/1163775139","volume":"58","author":"S. Sullivant","year":"2006","unstructured":"Sullivant S.: Compressed polytopes and statistical disclosure limitation. Tohoku Math. J. (2) 58(3), 433\u2013445 (2006)","journal-title":"Tohoku Math. J. (2)"},{"key":"425_CR25","unstructured":"Wiegele, A.: Nonlinear optimization techniques applied to combinatorial optimization problems. PhD thesis. Alpen-Adria-Universit\u00e4t Klagenfurt (2006)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0425-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-010-0425-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0425-z.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0425-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T18:35:49Z","timestamp":1559759749000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-010-0425-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,28]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["425"],"URL":"https:\/\/doi.org\/10.1007\/s10107-010-0425-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,28]]}}}