{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,13]],"date-time":"2024-07-13T17:18:29Z","timestamp":1720891109247},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,10,2]],"date-time":"2013-10-02T00:00:00Z","timestamp":1380672000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s10878-013-9662-4","type":"journal-article","created":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T04:34:52Z","timestamp":1380602092000},"page":"689-709","source":"Crossref","is-referenced-by-count":3,"title":["Rank bounds for a hierarchy of Lov\u00e1sz and Schrijver"],"prefix":"10.1007","volume":"30","author":[{"given":"Pratik","family":"Worah","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,10,2]]},"reference":[{"key":"9662_CR1","doi-asserted-by":"crossref","unstructured":"Au YH, Tun\u00e7el L (2011) Complexity analyses of Bienstock-Zuckerberg and Lasserre relaxations on the matching and stable set polytopes. In: IPCO, pp 14\u201326","DOI":"10.1007\/978-3-642-20807-2_2"},{"key":"9662_CR2","doi-asserted-by":"crossref","unstructured":"Beame P, Huynh T, Pitassi T (2010) Hardness amplification in proof complexity. In: STOC, pp 87\u201396","DOI":"10.1145\/1806689.1806703"},{"issue":"1","key":"9662_CR3","doi-asserted-by":"crossref","first-page":"269","DOI":"10.4086\/toc.2012.v008a012","volume":"8","author":"S Benabbas","year":"2012","unstructured":"Benabbas S, Georgiou K, Magen A, Tulsiani M (2012) SDP gaps from pairwise independence. Theory Comput 8(1):269\u2013289","journal-title":"Theory Comput"},{"key":"9662_CR4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge"},{"key":"9662_CR5","doi-asserted-by":"crossref","unstructured":"Buresh-Oppenheim J, Galesi N, Hoory S, Magen A, Pitassi T (2003) Rank bounds and integrality gaps for cutting planes procedures. In: FOCS, pp 318\u2013327","DOI":"10.1109\/SFCS.2003.1238206"},{"key":"9662_CR6","doi-asserted-by":"crossref","unstructured":"Charikar M, Makarychev K, Makarychev Y (2009) Integrality gaps for Sherali\u2013Adams relaxations. In: STOC, pp 283\u2013292","DOI":"10.1145\/1536414.1536455"},{"key":"9662_CR7","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1287\/moor.1060.0212","volume":"32","author":"KKH Cheung","year":"2007","unstructured":"Cheung KKH (2007) Computation of the lasserre ranks of some polytopes. Math Oper Res 32:88\u201394","journal-title":"Math Oper Res"},{"key":"9662_CR8","doi-asserted-by":"crossref","unstructured":"Chlamatac E, Tulsiani M (2010) Convex relaxations and integrality gaps. In: Handbook on semidefinite, cone and polynomial optimization","DOI":"10.1007\/978-1-4614-0769-0_6"},{"key":"9662_CR9","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1287\/moor.26.1.19.10593","volume":"26","author":"W Cook","year":"2001","unstructured":"Cook W, Dash S (2001) On the matrix-cut rank of polyhedra. Math Oper Res 26:19\u201331","journal-title":"Math Oper Res"},{"issue":"21\u201323","key":"9662_CR10","doi-asserted-by":"crossref","first-page":"2054","DOI":"10.1016\/j.tcs.2009.01.002","volume":"410","author":"SS Dantchev","year":"2009","unstructured":"Dantchev SS, Martin B, Rhodes MNC (2009) Tight rank lower bounds for the Sherali\u2013Adams proof system. Theor Comput Sci 410(21\u201323):2054\u20132063","journal-title":"Theor Comput Sci"},{"key":"9662_CR11","unstructured":"Dash S (2001) On the matrix-cut of polyhedra and their use in integer programming. PhD thesis. Department of Computer Science, Rice University"},{"key":"9662_CR12","unstructured":"de la Vega WF, Kenyon-Mathieu C (2007) Linear programming relaxations of MAX-CUT. In: SODA, pp 53\u201361"},{"issue":"2","key":"9662_CR13","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s004930050057","volume":"19","author":"F Eisenbrand","year":"1999","unstructured":"Eisenbrand F (1999) On the membership problem for the elementary closure of a polyhedron. Combinatorica 19(2):297\u2013300","journal-title":"Combinatorica"},{"issue":"4","key":"9662_CR14","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1287\/moor.26.4.796.10012","volume":"26","author":"MX Goemans","year":"2001","unstructured":"Goemans MX, Tun\u00e7el L (2001) When does the positive semidefiniteness constraint help in lifting procedures? Math Oper Res 26(4):796\u2013815","journal-title":"Math Oper Res"},{"key":"9662_CR15","doi-asserted-by":"crossref","unstructured":"Grigoriev D, Hirsch E, Pasechnik D (2002) Complexity of semi-algebraic proofs. In: STACS, LNCS, vol 2285, pp 419\u2013430","DOI":"10.1007\/3-540-45841-7_34"},{"key":"9662_CR16","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.dam.2007.07.021","volume":"156","author":"SP Hong","year":"2008","unstructured":"Hong SP, Tun\u00e7el L (2008) Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra. Discrete Appl Math 156:25\u201341","journal-title":"Discrete Appl Math"},{"key":"9662_CR17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511529948","volume-title":"Bounded arithmetic, propositional logic, and complexity theory","author":"J Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek J (1995) Bounded arithmetic, propositional logic, and complexity theory. Cambridge University Press, Cambridge"},{"issue":"3","key":"9662_CR18","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent M (2003) A comparison of the Sherali\u2013Adams, Lov\u00e1sz\u2013Schrijver, and Lasserre relaxations for 0\u20131 programming. Math Oper Res 28(3):470\u2013496","journal-title":"Math Oper Res"},{"key":"9662_CR19","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz L, Schrijver A (1991) Cones of matrices and set-functions and 0\u20131 optimization. SIAM J Optim 1:166\u2013190","journal-title":"SIAM J Optim"},{"key":"9662_CR20","doi-asserted-by":"crossref","unstructured":"Mathieu C, Sinclair A (2009) Sherali\u2013Adams relaxations of the matching polytope. In: STOC, pp 293\u2013302","DOI":"10.1145\/1536414.1536456"},{"key":"9662_CR21","doi-asserted-by":"crossref","unstructured":"Pitassi T, Segerlind N (2009) Exponential lower bounds and integrality gaps for tree-like Lov\u00e1sz\u2013Schrijver procedures. In: SODA, pp 355\u2013364","DOI":"10.1137\/1.9781611973068.40"},{"key":"9662_CR22","doi-asserted-by":"crossref","unstructured":"Pudlak P (1999) On the complexity of propositional calculus. In: Sets and proofs, invited papers from Logic Colloquium\u201997, Cambridge University Press, Cambridge, pp 197\u2013218","DOI":"10.1017\/CBO9781107325944.010"},{"key":"9662_CR23","unstructured":"Razborov AA (2001) Proof complexity of Pigeonhole principles. In: 5th Developments in language theory, LNCS, vol 2295, pp 100\u2013116"},{"key":"9662_CR24","doi-asserted-by":"crossref","unstructured":"Rudich S, Wigderson A (2004) Computational complexity theory. AMS, IAS\/Park City Mathematics Series","DOI":"10.1090\/pcms\/010"},{"issue":"4","key":"9662_CR25","doi-asserted-by":"crossref","first-page":"417","DOI":"10.2178\/bsl\/1203350879","volume":"13","author":"N Segerlind","year":"2007","unstructured":"Segerlind N (2007) The complexity of propositional proofs. Bull Symb Log 13(4):417\u2013481","journal-title":"Bull Symb Log"},{"key":"9662_CR26","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and Convex hull representations for zero-one programming problems. SIAM J Disc Math 3:411\u2013430","journal-title":"SIAM J Disc Math"},{"key":"9662_CR27","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1287\/opre.46.3.396","volume":"46","author":"HD Sherali","year":"1998","unstructured":"Sherali HD, Adams WP, Driscoll PJ (1998) Exploiting special structures in constructing a hierarchy for relaxations for 0\u20131 mixed integer problems. Oper Res 46:396\u2013405","journal-title":"Oper Res"},{"key":"9662_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.24.1.1","volume":"24","author":"T Stephen","year":"1999","unstructured":"Stephen T, Tun\u00e7el L (1999) On a representation of the matching polytope via semidefinite liftings. Math Oper Res 24:1\u20137","journal-title":"Math Oper Res"},{"key":"9662_CR29","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2004","unstructured":"Vazirani VV (2004) Approximation algorithms. Springer, New York"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9662-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9662-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9662-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,27]],"date-time":"2019-07-27T13:36:35Z","timestamp":1564234595000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9662-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,2]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["9662"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9662-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,2]]}}}