{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T06:02:47Z","timestamp":1751349767822},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_28","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T00:01:36Z","timestamp":1282867296000},"page":"366-379","source":"Crossref","is-referenced-by-count":11,"title":["Improving Integrality Gaps via Chv\u00e1tal-Gomory Rounding"],"prefix":"10.1007","author":[{"given":"Mohit","family":"Singh","sequence":"first","affiliation":[]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"28_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.4086\/toc.2006.v002a002","volume":"2","author":"S. Arora","year":"2006","unstructured":"Arora, S., Bollob\u00e1s, B., Lov\u00e1sz, L., Tourlakis, I.: Proving Integrality Gaps without Knowing the Linear Program. Theory of Computing\u00a02(1), 19\u201351 (2006)","journal-title":"Theory of Computing"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Bollob\u00e1s, B., Lov\u00e1sz, L.: Proving Integrality Gaps without Knowing the Linear Program. In: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS), pp. 313\u2013322 (2002)","DOI":"10.1109\/SFCS.2002.1181954"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Beame, P., Huynh, T., Pitassi, T.: Hardness amplification in proof complexity. In: Proceedings of the Fourty-Second Annual ACM Symposium on Theory of Computing, STOC (2010)","DOI":"10.1145\/1806689.1806703"},{"key":"28_CR4","unstructured":"Berman, P., Karpinski, M.: Improved Approximation Lower Bounds on Small Occurrence Optimization. In: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a010, p. 008 (2003)"},{"issue":"1","key":"28_CR5","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/s10107-005-0598-z","volume":"105","author":"D. Bienstock","year":"2006","unstructured":"Bienstock, D., Zuckerberg, M.: Approximate fixed-rank closures of covering problems. Math. Program.\u00a0105(1), 9\u201327 (2006)","journal-title":"Math. Program."},{"issue":"1-2","key":"28_CR6","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.E., Schulz, A.S.: On the Chvtal Rank of Polytopes in the 0\/1 Cube. Discrete Applied Mathematics\u00a098(1-2), 21\u201327 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"28_CR7","unstructured":"Buresh-Oppenheim., J., Galesi, N., Hoory, S., Magen, A., Pitassi, T.: Rank Bounds and Integrality Gaps for Cutting Planes Procedures. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, October 11-14 (2003)"},{"key":"28_CR8","first-page":"87","volume":"12","author":"M. Calczy\u0144ska-Karlowicz","year":"1964","unstructured":"Calczy\u0144ska-Karlowicz, M.: Theorem on Families of Finite Sets. Bulletin de lAcad\u00e9mie Polonaise des Sciences. S\u00e9rie des Sciences Math\u00e9matiques, Astronomiques et Physiques\u00a012, 87\u201389 (1964)","journal-title":"Bulletin de lAcad\u00e9mie Polonaise des Sciences. S\u00e9rie des Sciences Math\u00e9matiques, Astronomiques et Physiques"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Chan, Y.H., Lau, L.C.: On Linear and Semidefinite Programming Relaxations for Hypergraph Matching. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) (January 2010)","DOI":"10.1137\/1.9781611973075.122"},{"key":"28_CR10","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, STOC 2009, pp. 283\u2013292 (2009)","DOI":"10.1145\/1536414.1536455"},{"key":"28_CR11","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 Math.\u00a04, 305\u2013337 (1973)","journal-title":"Discrete Math."},{"key":"28_CR12","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114\/115","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\/115, 455\u2013499 (1989)","journal-title":"Linear Algebra and its Applications"},{"issue":"1","key":"28_CR13","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s10479-006-0100-1","volume":"149","author":"G. Cornu\u00e9jols","year":"2007","unstructured":"Cornu\u00e9jols, G.: Revival of the Gomory cuts in the 1990\u2019s. Annals of Operations Research\u00a0149(1), 63\u201366 (2007)","journal-title":"Annals of Operations Research"},{"key":"28_CR14","unstructured":"Dash, S.: On the Matrix Cuts of Lovsz and Schrijver and their use in Integer Programming. PhD thesis, Department of Computer Science, Rice University (March 2001)"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/3-540-47867-1_11","volume-title":"Integer Programming and Combinatorial Optimization","author":"S. Dash","year":"2002","unstructured":"Dash, S.: An Exponential Lower Bound on the Length of Some Classes of Branch-and-Cut Proofs. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 145\u2013160. Springer, Heidelberg (2002)"},{"key":"28_CR16","unstructured":"de la Vega, W.F., Kenyon-Mathieu, C.: Linear Programming Relaxations of Maxcut. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2007, pp. 53\u201361 (2007)"},{"key":"28_CR17","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s004930050057","volume":"19","author":"F. Eisenbrand","year":"1999","unstructured":"Eisenbrand, F.: On the Membership Problem for the Elementary Closure of a Polyhedron. Combinatorica\u00a019, 297\u2013300 (1999)","journal-title":"Combinatorica"},{"key":"28_CR18","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.S.: Bounds on the Chvtal rank of polytopes in the 0\/1-cube. Combinatorica\u00a023, 245\u2013261 (2003)","journal-title":"Combinatorica"},{"key":"28_CR19","first-page":"609","volume-title":"Proceedings of Colloquia Mathematica Societatis J\u00e1nos Bolyai, Infinite and Finite Sets","author":"P. Erd\u00f6s","year":"1973","unstructured":"Erd\u00f6s, P., Lov\u00e1sz, L.: Problems and Results on 3- chromatic Hypergraphs and Some Related Questions. In: Hajnal, A., Rado, R., S\u00f3s, V.T. (eds.) Proceedings of Colloquia Mathematica Societatis J\u00e1nos Bolyai, Infinite and Finite Sets, vol.\u00a010, pp. 609\u2013627. Keszthely, Hungary (1973)"},{"key":"28_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/3-540-48777-8_11","volume-title":"Integer Programming and Combinatorial Optimization","author":"F. Eisenbrand","year":"1999","unstructured":"Eisenbrand, F., Schulz, A.S.: Bounds on the chv\u00e1tal rank of polytopes in the 0\/1-cube. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol.\u00a01610, pp. 137\u2013150. Springer, Heidelberg (1999)"},{"key":"28_CR21","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., 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"},{"issue":"5","key":"28_CR22","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"R.E. Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the American Mathematical Society\u00a064(5), 275\u2013278 (1958)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"28_CR23","first-page":"211","volume-title":"Combinatorial Analysis. Symposia in Applied Mathematics X","author":"R.E. Gomory","year":"1960","unstructured":"Gomory, R.E.: Solving Linear Programming Problems in Integers. In: Bellman, R., Hall Jr., M. (eds.) Combinatorial Analysis. Symposia in Applied Mathematics X, pp. 211\u2013215. American Mathematical Society, Providence (1960)"},{"key":"28_CR24","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 Lovsz-Schrijver Hierarchy. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), pp. 702\u2013712 (2007)","DOI":"10.1109\/FOCS.2007.35"},{"key":"28_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/1109557.1109569","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm SODA 2006","author":"A. Gupta","year":"2006","unstructured":"Gupta, A., Talwar, K.: Approximating Unique Games. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm SODA 2006, pp. 99\u2013106. ACM, New York (2006)"},{"key":"28_CR26","series-title":"Lecture Notes in Computer Science","first-page":"59","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Hazan","year":"2003","unstructured":"Hazan, E., Safra, M., Schwartz, O.: On the Complexity of Approximating k-Dimensional Matching. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 59\u201370. Springer, Heidelberg (2003)"},{"key":"28_CR27","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the Size of Systems of Sets Every t of which have an SDR, with an Application to the Worst-case Ratio of Heuristics for Packing Problems. SIAM Journal on Discrete Mathematics\u00a02, 68\u201372 (1989)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"28_CR28","doi-asserted-by":"crossref","unstructured":"Khot, S., Saket, R.: SDP Integrality Gaps with Local \u21131-Embeddability. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science, FOCS (2009)","DOI":"10.1109\/FOCS.2009.37"},{"key":"28_CR29","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":"3","key":"28_CR30","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. Mathematics of Operations Research\u00a028(3), 470\u2013496 (2003)","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"28_CR31","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. Optimization\u00a01(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optimization"},{"key":"28_CR32","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, STOC 2009, pp. 293\u2013302 (2009)","DOI":"10.1145\/1536414.1536456"},{"key":"28_CR33","doi-asserted-by":"crossref","unstructured":"Pitassi, T., Segerlind, N.: Exponential lower bounds and Integrality gaps for Tree-like Lovsz-Schrijver Procedures. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, January 04-06 (2009)","DOI":"10.1137\/1.9781611973068.40"},{"issue":"3","key":"28_CR34","doi-asserted-by":"publisher","first-page":"981","DOI":"10.2307\/2275583","volume":"62","author":"P. Pudl\u00e1k","year":"1997","unstructured":"Pudl\u00e1k, P.: Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations. Journal of Symbolic Logic\u00a062(3), 981\u2013998 (1997)","journal-title":"Journal of Symbolic Logic"},{"key":"28_CR35","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Integrality Gaps for Strong SDP Relaxations of Unique Games. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science, FOCS (2009)","DOI":"10.1109\/FOCS.2009.73"},{"key":"28_CR36","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear Level Lasserre Lower Bounds for Certain k-CSPs. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"issue":"3","key":"28_CR37","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."},{"key":"28_CR38","doi-asserted-by":"crossref","unstructured":"Singh, M., Talwar, K.: Improving Integrality Gaps via chv\u00e1tal-Gomory Rounding (2010) (manuscript)","DOI":"10.1007\/978-3-642-15369-3_28"},{"key":"28_CR39","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: CSP gaps and Reductions in the Lasserre Hierarchy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 303\u2013312 (2009)","DOI":"10.1145\/1536414.1536457"},{"key":"28_CR40","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/0095-8956(85)90043-7","volume":"39","author":"Z.. Tuza","year":"1985","unstructured":"Tuza, Z.: Critical Hypergraphs and Intersecting Set-pair Systems. Journal of Combinatorial Theory (B)\u00a039, 134\u2013145 (1985)","journal-title":"Journal of Combinatorial Theory (B)"},{"key":"28_CR41","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0166-218X(87)90074-6","volume":"16","author":"Z.. Tuza","year":"1987","unstructured":"Tuza, Z.: On Two Intersecting Set Systems and k- continuous Boolean functions. Discrete Applied Mathematics\u00a016, 183\u2013185 (1987)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:05:25Z","timestamp":1606169125000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}