{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:40:40Z","timestamp":1725586840998},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208065"},{"type":"electronic","value":"9783642208072"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_2","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T09:58:49Z","timestamp":1308391129000},"page":"14-26","source":"Crossref","is-referenced-by-count":7,"title":["Complexity Analyses of Bienstock\u2013Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes"],"prefix":"10.1007","author":[{"given":"Yu Hin","family":"Au","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Levent","family":"Tun\u00e7el","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"2_CR1","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0166-218X(03)00337-8","volume":"134","author":"N.E. Aguilera","year":"2004","unstructured":"Aguilera, N.E., Bianchi, S.M., Nasini, G.L.: Lift and project relaxations for the matching and related polytopes. Discrete Appl. Math.\u00a0134(1-3), 193\u2013212 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"1-3","key":"2_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00136-X","volume":"89","author":"E. Balas","year":"1998","unstructured":"Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math.\u00a089(1-3), 3\u201344 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"3, Ser. A","key":"2_CR3","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E. Balas","year":"1993","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Programming\u00a058(3, Ser. A), 295\u2013324 (1993)","journal-title":"Math. Programming"},{"key":"2_CR4","unstructured":"Benabbas, S., Georgiou, K., Magen, A.: The Sherali-Adams system applied to vertex cover: why Borsuk graphs fool strong LPs and some tight integrality gaps for SDPs (2010) (extended Abstract)"},{"issue":"1","key":"2_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/S1052623402420346","volume":"15","author":"D. Bienstock","year":"2004","unstructured":"Bienstock, D., Zuckerberg, M.: Subset algebra lift operators for 0-1 integer programming. SIAM J. Optim.\u00a015(1), 63\u201395 (2004)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1287\/moor.26.1.19.10593","volume":"26","author":"W. Cook","year":"2001","unstructured":"Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Math. Oper. Res.\u00a026(1), 19\u201330 (2001)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2_CR7","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1137\/040605849","volume":"16","author":"K.K.H. Cheung","year":"2005","unstructured":"Cheung, K.K.H.: On Lov\u00e1sz-Schrijver lift-and-project procedures on the Dantzig-Fulkerson-Johnson relaxation of the TSP. SIAM J. Optim.\u00a016(2), 380\u2013399 (2005)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2_CR8","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1287\/moor.1060.0212","volume":"32","author":"K.K.H. Cheung","year":"2007","unstructured":"Cheung, K.K.H.: Computation of the Lasserre ranks of some polytopes. Math. Oper. Res.\u00a032(1), 88\u201394 (2007)","journal-title":"Math. Oper. Res."},{"key":"2_CR9","unstructured":"Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Tight integrality gaps for vertex cover SDPs in the Lov\u00e1sz-Schrijver hierarchy. Electronic Colloquium on Computational Complexity (ECCC)\u00a013(152) (2006)"},{"issue":"4","key":"2_CR10","doi-asserted-by":"publisher","first-page":"2097","DOI":"10.1137\/090746525","volume":"20","author":"J. Gouveia","year":"2010","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.R.: Theta bodies for polynomial ideals. SIAM Journal on Optimization\u00a020(4), 2097\u20132118 (2010)","journal-title":"SIAM Journal on Optimization"},{"issue":"4","key":"2_CR11","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1287\/moor.26.4.796.10012","volume":"26","author":"M.X. Goemans","year":"2001","unstructured":"Goemans, M.X., Tun\u00e7el, L.: When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res.\u00a026(4), 796\u2013815 (2001)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"2_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.dam.2007.07.021","volume":"156","author":"S.-P. Hong","year":"2008","unstructured":"Hong, S.-P., Tun\u00e7el, L.: Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra. Discrete Appl. Math.\u00a0156(1), 25\u201341 (2008)","journal-title":"Discrete Appl. Math."},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-45535-3_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"J.B. Lasserre","year":"2001","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 293\u2013303. Springer, Heidelberg (2001)"},{"issue":"2","key":"2_CR14","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/S1052623400379371","volume":"12","author":"M. Laurent","year":"2001","unstructured":"Laurent, M.: Tighter linear and semidefinite relaxations for max-cut based on the Lov\u00e1sz-Schrijver lift-and-project procedure. SIAM J. Optim.\u00a012(2), 345\u2013375 (2001\/2002)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2_CR15","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-1 programming. Math. Oper. Res.\u00a028(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2_CR16","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-1 optimization. SIAM J. Optim.\u00a01(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"issue":"1-3, Ser. B","key":"2_CR17","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10107-003-0407-5","volume":"98","author":"L. Lipt\u00e1k","year":"2003","unstructured":"Lipt\u00e1k, L., Tun\u00e7el, L.: The stable set problem and the lift-and-project ranks of graphs. Math. Program.\u00a098(1-3, Ser. B), 319\u2013353 (2003); Integer programming (Pittsburgh, PA, 2002)","journal-title":"Math. Program."},{"key":"2_CR18","volume-title":"STOC 2009","author":"C. Mathieu","year":"2009","unstructured":"Mathieu, C., Sinclair, A.: Sherali-Adams relaxations of the matching polytope. In: STOC 2009. ACM Press, New York (2009)"},{"issue":"3","key":"2_CR19","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. Discrete Math.\u00a03(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"2_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.24.1.1","volume":"24","author":"T. Stephen","year":"1999","unstructured":"Stephen, T., Tun\u00e7el, L.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res.\u00a024(1), 1\u20137 (1999)","journal-title":"Math. Oper. Res."},{"key":"2_CR21","first-page":"6","volume-title":"IEEE Conference on Computational Complexity","author":"G. Schoenebeck","year":"2006","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: A linear round lower bound for Lov\u00e1sz-Schrijver SDP relaxations of vertex cover. In: IEEE Conference on Computational Complexity, pp. 6\u201398. IEEE Computer Society, Los Alamitos (2006)"},{"key":"2_CR22","unstructured":"Zuckerberg, M.: A Set Theoretic Approach to Lifting Procedures for 0,1 Integer Programming. PhD thesis, Columbia University (2003)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,28]],"date-time":"2019-03-28T22:02:01Z","timestamp":1553810521000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}