{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T11:53:51Z","timestamp":1771329231737,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,6,7]],"date-time":"2005-06-07T00:00:00Z","timestamp":1118102400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2006,3]]},"DOI":"10.1007\/s10107-005-0604-5","type":"journal-article","created":{"date-parts":[[2005,6,7]],"date-time":"2005-06-07T15:15:34Z","timestamp":1118157334000},"page":"159-175","source":"Crossref","is-referenced-by-count":19,"title":["Exploring the Relationship Between Max-Cut and Stable Set Relaxations"],"prefix":"10.1007","volume":"106","author":[{"given":"Monia","family":"Giandomenico","sequence":"first","affiliation":[]},{"given":"Adam N.","family":"Letchford","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"604_CR1","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10107-003-0423-5","volume":"97","author":"Avis","year":"2003","unstructured":"Avis, D., Umemoto, J.: Stronger linear programming relaxations of max-cut. Math. Program. 97, 451\u2013469 (2003)","journal-title":"Math. Program."},{"key":"604_CR2","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"Barahona","year":"1986","unstructured":"Barahona, F., Mahjoub, A.R.: On the cut polytope. Math. Program. 36, 157\u2013173 (1986)","journal-title":"Math. Program."},{"key":"604_CR3","unstructured":"Bornd\u00f6rfer, R.: Aspects of Set Packing, Partitioning and Covering. Doctoral Thesis, Technical University of Berlin, 1998"},{"key":"604_CR4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1080\/10556789408805564","volume":"3","author":"Simone","year":"1994","unstructured":"De Simone, C., Rinaldi, G.: A cutting plane algorithm for the max-cut problem. Opt. Methods and Software 3, 195\u2013214 (1994)","journal-title":"Opt. Methods and Software"},{"key":"604_CR5","doi-asserted-by":"crossref","unstructured":"Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Berlin: Springer-Verlag, 1997","DOI":"10.1007\/978-3-642-04295-9"},{"key":"604_CR6","doi-asserted-by":"crossref","unstructured":"Fischer, I., Gruber, G., Rendl, F., Sotirov, R.: Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and Equipartition. To appear in Math. Program, 2005","DOI":"10.1007\/s10107-005-0661-9"},{"key":"604_CR7","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0095-8956(72)90032-9","volume":"12","author":"Fulkerson","year":"1972","unstructured":"Fulkerson, D.R.: Anti-blocking polyhedra. J. Comb. Th. (B) 12, 50\u201371 (1972)","journal-title":"J. Comb. Th. (B)"},{"key":"604_CR8","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Ass. Comp. Mach. 42, 1115\u20131145 (1995)","journal-title":"J. Ass. Comp. Mach."},{"key":"604_CR9","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.J.: Geometric Algorithms in Combinatorial Optimization. New York: Wiley, 1988","DOI":"10.1007\/978-3-642-97881-4"},{"key":"604_CR10","doi-asserted-by":"crossref","first-page":"1014","DOI":"10.1137\/S1052623401394092","volume":"13","author":"Gruber","year":"2003","unstructured":"Gruber, G., Rendl, F.: Computational experience with stable set relaxations. SIAM J. Optimization 13, 1014\u20131028 (2003)","journal-title":"SIAM J. Optimization"},{"key":"604_CR11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1\u2212\u2208. Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"604_CR12","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF02579314","volume":"2","author":"Juh\u00e1sz","year":"1982","unstructured":"Juh\u00e1sz, F.: The asymptotic behaviour of Lov\u00e1sz' \u03b8 function for random graphs. Combinatorica 2, 153\u2013155 (1982)","journal-title":"Combinatorica"},{"key":"604_CR13","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01589098","volume":"45","author":"Laurent","year":"1989","unstructured":"Laurent, M.: A generalization of antiwebs to independence systems and their canonical facets. Math. Program. 45, 97\u2013108 (1989)","journal-title":"Math. Program."},{"key":"604_CR14","doi-asserted-by":"crossref","unstructured":"Laurent, M., Poljak, S.: On a positive semidefinite relaxation of the cut polytope. Lin. Alg. Appl. 223\/224, 439\u2013461 (1995)","DOI":"10.1016\/0024-3795(95)00271-R"},{"key":"604_CR15","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1137\/0617031","volume":"17","author":"Laurent","year":"1996","unstructured":"Laurent, M., Poljak, S.: Gap inequalities for the cut polytope. SIAM Journal on Matrix Analysis 17, 530\u2013547 (1996)","journal-title":"SIAM Journal on Matrix Analysis"},{"key":"604_CR16","first-page":"225","volume":"77","author":"Laurent","year":"1997","unstructured":"Laurent, M., Poljak, S., Rendl, F.: Connections between semidefinite relaxations for the max-cut and stable set problems. Math. Program. 77, 225\u2013246 (1997)","journal-title":"Math. Program."},{"key":"604_CR17","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: Normal hypergraphs and the perfect graph conjecture. Discr. Math. 2, 253\u2013267 (1972)","journal-title":"Discr. Math."},{"key":"604_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Th. 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Th."},{"key":"604_CR19","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.J.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optimization 1, 166\u2013190 (1991)","journal-title":"SIAM J. Optimization"},{"key":"604_CR20","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"Padberg","year":"1973","unstructured":"Padberg, M.W.: On the facial structure of set packing polyhedra. Math. Prog. 5, 199\u2013215 (1973)","journal-title":"Math. Prog."},{"key":"604_CR21","doi-asserted-by":"crossref","unstructured":"Schrijver, A.J.: A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans. Inf. Th. IT-25, 425\u2013429 (1979)","DOI":"10.1109\/TIT.1979.1056072"},{"key":"604_CR22","unstructured":"Shepherd, B.: The theta body and imperfection. In R. Alfonsion & B. Reed (Eds.), Perfect Graphs. Wiley, 2001"},{"key":"604_CR23","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/0012-365X(75)90077-1","volume":"12","author":"Trotter","year":"1975","unstructured":"Trotter, L.E.: A class of facet-producing graphs for vertex packing polyhedra. Discr. Math. 12, 373\u2013388 (1975)","journal-title":"Discr. Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0604-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-005-0604-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0604-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T15:33:17Z","timestamp":1586273597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-005-0604-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6,7]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["604"],"URL":"https:\/\/doi.org\/10.1007\/s10107-005-0604-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6,7]]}}}