{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:26:10Z","timestamp":1725557170705},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130359"},{"type":"electronic","value":"9783642130366"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13036-6_34","type":"book-chapter","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T08:36:09Z","timestamp":1275986169000},"page":"450-463","source":"Crossref","is-referenced-by-count":10,"title":["On the Rank of Cutting-Plane Proof Systems"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Pokutta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas S.","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"34_CR1","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E. Balas","year":"1993","unstructured":"Balas, E., Ceria, S., Cornuejols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming\u00a058, 295\u2013324 (1993)","journal-title":"Mathematical Programming"},{"key":"34_CR2","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0166-218X(99)00156-0","volume":"98","author":"A. Bockmayr","year":"1999","unstructured":"Bockmayr, A., Eisenbrand, F., Hartmann, M., Schulz, A.: On the Chv\u00e1tal rank of polytopes in the 0\/1 cube. Discrete Applied Mathematics\u00a098, 21\u201327 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"Bonet, M., Pitassi, T., Raz, R.: Lower bounds for cutting planes proofs with small coefficients. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 575\u2013584 (1995)","DOI":"10.1145\/225058.225275"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 283\u2013292 (2009)","DOI":"10.1145\/1536414.1536455"},{"key":"34_CR5","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V. Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics\u00a04, 305\u2013337 (1973)","journal-title":"Discrete Mathematics"},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114","author":"V. Chv\u00e1tal","year":"1989","unstructured":"Chv\u00e1tal, V., Cook, W., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear algebra and its applications\u00a0114, 455\u2013499 (1989)","journal-title":"Linear algebra and its applications"},{"key":"34_CR7","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. Mathematics of Operations Research\u00a026, 19\u201330 (2001)","journal-title":"Mathematics of Operations Research"},{"key":"34_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-006-0086-0","volume":"112","author":"G. Cornu\u00e9jols","year":"2008","unstructured":"Cornu\u00e9jols, G.: Valid inequalities for mixed integer linear programs. Mathematical Programming\u00a0112, 3\u201344 (2008)","journal-title":"Mathematical Programming"},{"key":"34_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0167-6377(00)00067-5","volume":"28","author":"G. Cornuejols","year":"2001","unstructured":"Cornuejols, G., Li, Y.: Elementary closures for integer programs. Operations Research Letters\u00a028, 1\u20138 (2001)","journal-title":"Operations Research Letters"},{"key":"34_CR10","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s10107-002-0302-5","volume":"93","author":"G. Cornu\u00e9jols","year":"2002","unstructured":"Cornu\u00e9jols, G., Li, Y.: A connection between cutting plane theory and the geometry of numbers. Mathematical Programming\u00a093, 123\u2013127 (2002)","journal-title":"Mathematical Programming"},{"key":"34_CR11","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s101070100250","volume":"91","author":"G. Cornu\u00e9jols","year":"2002","unstructured":"Cornu\u00e9jols, G., Li, Y.: On the rank of mixed 0,1 polyhedra. Mathematical Programming\u00a091, 391\u2013397 (2002)","journal-title":"Mathematical Programming"},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"Dantchev, S.: Rank complexity gap for Lov\u00e1sz-Schrijver and Sherali-Adams proof systems. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 311\u2013317 (2007)","DOI":"10.1145\/1250790.1250837"},{"key":"34_CR13","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1287\/moor.1050.0151","volume":"30","author":"S. Dash","year":"2005","unstructured":"Dash, S.: An exponential lower bound on the length of some classes of branch-and-cut proofs. Mathematics of Operations Research\u00a030, 678\u2013700 (2005)","journal-title":"Mathematics of Operations Research"},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00493-003-0020-5","volume":"23","author":"F. Eisenbrand","year":"2003","unstructured":"Eisenbrand, F., Schulz, A.: Bounds on the Chv\u00e1tal rank of polytopes in the 0\/1-cube. Combinatorica\u00a023, 245\u2013261 (2003)","journal-title":"Combinatorica"},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2-o(1) for vertex cover SDPs in the Lov\u00e1sz-Schrijver hierarchy. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 702\u2013712 (2007)","DOI":"10.1109\/FOCS.2007.35"},{"key":"34_CR16","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1287\/moor.26.4.796.10012","volume":"26","author":"M. Goemans","year":"2001","unstructured":"Goemans, M., Tuncel, L.: When does the positive semidefiniteness constraint help in lifting procedures? Mathematics of Operations Research\u00a026, 796\u2013815 (2001)","journal-title":"Mathematics of Operations Research"},{"key":"34_CR17","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"R. Gomory","year":"1958","unstructured":"Gomory, R.: Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society\u00a064, 275\u2013278 (1958)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"34_CR18","first-page":"211","volume-title":"Proceedings of Symposia in Applied Mathematics X","author":"R. Gomory","year":"1960","unstructured":"Gomory, R.: Solving linear programming problems in integers. In: Bellman, R., Hall, M. (eds.) Proceedings of Symposia in Applied Mathematics X, pp. 211\u2013215. American Mathematical Society, Providence (1960)"},{"key":"34_CR19","first-page":"269","volume-title":"Recent Advances in Mathematical Programming","author":"R. Gomory","year":"1963","unstructured":"Gomory, R.: An algorithm for integer solutions to linear programs. In: Recent Advances in Mathematical Programming, pp. 269\u2013302. McGraw-Hill, New York (1963)"},{"key":"34_CR20","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. Lasserre","year":"2001","unstructured":"Lasserre, J.: 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)"},{"key":"34_CR21","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 Journal on Optimization\u00a01, 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"key":"34_CR22","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Sinclair, A.: Sherali-Adams relaxations of the matching polytope. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 293\u2013302 (2009)","DOI":"10.1145\/1536414.1536456"},{"key":"34_CR23","unstructured":"Pokutta, S., Schulz, A.: A note on 0\/1 polytopes without integral points and with maximal rank (2009) (preprint)"},{"key":"34_CR24","unstructured":"Pokutta, S., Schulz, A.: On the connection of the Sherali-Adams closure and border bases (2009) (submitted)"},{"key":"34_CR25","first-page":"197","volume-title":"Sets and Proofs, Invited Papers from Logic Colloquium \u201997","author":"P. Pudlak","year":"1999","unstructured":"Pudlak, P.: On the complexity of propositional calculus. In: Sets and Proofs, Invited Papers from Logic Colloquium \u201997, pp. 197\u2013218. Cambridge University Press, Cambridge (1999)"},{"key":"34_CR26","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPs. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"key":"34_CR27","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lov\u00e1sz-Schrijver LP relaxations of vertex cover and max cut. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 302\u2013310 (2007)","DOI":"10.1145\/1250790.1250836"},{"key":"34_CR28","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H. Sherali","year":"1990","unstructured":"Sherali, H., Adams, W.: A hierarchy of relaxations between the continuous and convex representations for zero-one programming problems. SIAM Journal on Discrete Mathematics\u00a03, 411\u2013430 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13036-6_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:00:25Z","timestamp":1606168825000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13036-6_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130359","9783642130366"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13036-6_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}