Rank Bounds and Integrality Gaps for Cutting Planes Procedures

by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi

Theory of Computing, Volume 2(4), pp. 65-90, 2006

Bibliography with links to cited articles

[1] M. Alekhnovich, S. Arora, and I. Tourlakis: Towards strong approximability results in the Lovász-Schrijver hierarchy. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 294-303, 2005. [STOC:1060590.1060634].
[2] S. Arora, B. Bollobás, and L. Lovász: Proving integrality gaps without knowing the linear program. In Proceedings of the Forty-Third Annual Symposium on Foundations of Computer Science, pp. 313-322, 2002. [FOCS:10.1109/SFCS.2002.1181954].
[3] S. Arora, B. Bollobás, L. Lovász, and I. Tourlakis: Proving integrality gaps without knowing the linear program. Theory of Computing, 2(2):19-51, 2006. [ToC:v002/a002].
[4] S. Arora, S. Rao, and U. Vazirani: Expander flows, geometric embeddings and graph partitioning. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 222-231, Chicago, IL, June 2004. [STOC:1007352.1007355].
[5] A. Atserias, M.L. Bonet, and J. Levy: On Chvátal rank and cutting planes proofs. Technical Report TR03-041, ECCC, 2003. [ECCC:TR03-041].
[6] E. Ben-Sasson and A. Wigderson: Short proofs are narrow - Resolution made simple. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 517-526, Atlanta, GA, May 1999. [STOC:301250.301392].
[7] A. Bockmayr, F. Eisenbrand, M.E. Hartmann, and A.S. Schulz: On the Chvátal rank of polytopes in the 0/1 cube. Discrete Applied Mathematics, 98(1-2):21-27, October 1999. [damath:10.1016/S0166-218X(99)00156-0].
[8] M.L. Bonet and N. Galesi: A study of proof search algorithms for Resolution and Polynomial Calculus. In Proceedings of the Fortieth Annual Symposium on Foundations of Computer Science, pp. 422-431, 1999. [FOCS:10.1109/SFFCS.1999.814614].
[9] J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen, and T. Pitassi: Rank bounds and integrality gaps for cutting planes procedures. In Proceedings of the Forty-Fourth Annual Symposium on Foundations of Computer Science, pp. 318-327, 2003. [FOCS:10.1109/SFCS.2003.1238206].
[10] V. Chvátal: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics, 4(4):305-337, 1973. [DiscMath:10.1016/0012-365X(73)90167-2].
[11] V. Chvátal, W. Cook, and M. Hartmann: On cutting-plane proofs in combinatorial optimization. Linear Algebra and its Applications, 114/115:455-499, 1989. [laappl:10.1016/0024-3795(89)90476-X].
[12] V. Chvátal and E. Szemerédi: Many hard examples for resolution. Journal of the ACM, 35(4):759-768, 1988. [JACM:48014.48016].
[13] M. Clegg, J. Edmonds, and R. Impagliazzo: Using the Gröbner basis algorithm to find proofs of unsatisfiability. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 174-183, Philadelphia, PA, May 1996. [STOC:237814.237860].
[14] W. Cook, C.R. Coullard, and G. Turán: On the complexity of cutting plane proofs. Discrete Applied Mathematics, 18:25-38, 1987. [damath:10.1016/0166-218X(87)90039-4].
[15] S. Dash: On the matrix cuts of Lovász and Schrijver and their use in Integer Programming. PhD thesis, Department of Computer Science, Rice University, March 2001.
[16] S. Dash: An exponential lower bound on the length of some classes of branch-and-cut proofs. Mathematics of Operations Research, 30(3):678-700, 2005.
[17] M. Davis and H. Putnam: A computing procedure for quantification theory. Journal of the ACM, 7(3):201-215, 1960. [JACM:321033.321034].
[18] Friedrich Eisenbrand and Andreas S. Schulz: Bounds on the Chvátal rank of polytopes in the 0/1-cube. In Proceedings of the Seventh Annual Conference on Integer Programming and Combinatorial Optimization, number 1610 in Lecture Notes in Computer Science, pp. 137-150, 1999. [IPCO:y0ruretrf6paebe1]. [ .pdf ]
[19] U. Feige and R. Krauthgamer: The probable value of Lovász-Schrijver relaxations for maximum independent set. SIAM Journal on Computing, 32(2):345-370, 2003. [SICOMP:10.1137/S009753970240118X].
[20] M. Goemans and L. Tunçel: When does the postive semidefiniteness constraint help in lifting procedures. Mathematics of Operations Research, 26:796-815, 2001.
[21] M. Goemans and D. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, 1995. [JACM:227683.227684].
[22] R.E. Gomory: Solving linear programming problems in integers. In R. Bellman and M. Hall, Jr., editors, Combinatorial Analysis, pp. 211-215, Providence, RI, 1960. Symposia in Applied Mathematics X, American Mathematical Society.
[23] D. Grigoriev, E.A. Hirsch, and D.V. Pasechnik: Complexity of semi-algebraic proofs. In Proceedings of the Eighteenth Annual Symposium on Theoretical Aspects of Computer Science, number 2285 in Lecture Notes in Computer Science, pp. 419-430, 2002. [STACS:t7lpe5yvaphpp0j6]. [ .html ]
[24] D. Grigoriev, E.A. Hirsch, and D.V. Pasechnik: Exponential lower bound for static semi-algebraic proofs. In Proceedings of the Twenty-Ninth International Colloquium on Automata, Languages and Programming, number 2380 in Lecture notes in computer science, pp. 257-268, 2002. [ICALP:j2k07b37hmw2pfgw].
[25] Martin Grötschel, László Lovász, and Alexander Schrijver: Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993.
[26] A. Haken: The intractability of resolution. Theoretical Computer Science, 39:297-305, 1985. [TCS:10.1016/0304-3975(85)90144-6].
[27] Mark Hartmann: Cutting Planes and the Complexity of the Integer Hull. PhD thesis, Cornell University, 1988. Department of Operations Research and Industrial Engineering.
[28] J. Håstad: Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. [JACM:502090.502098].
[29] E.A. Hirsch and A. Kojevnikov: Several notes on the power of Gomory-Chvátal cuts. Technical Report TR03-012, ECCC, 2003. [ECCC:TR03-012].
[30] R. Impagliazzo, T. Pitassi, and A. Urquhart: Upper and lower bounds on tree-like cutting planes proofs. In Proceedings from Logic in Computer Science, 1994. [lics:10.1109/LICS.1994.316069].
[31] L.G. Khachian: A polynomial time algorithm for linear programming. Doklady Akademii Nauk SSSR, n.s., 244(5):1093-1096, 1979. English translation in Soviet Math. Dokl. 20, 191-194.
[32] B. Krishnamurthy: Short proofs for tricky formulas. Acta Informatica, 22:253-275, 1985. [ActaInf:mp65776636126242].
[33] L. Lovász and A. Schrijver: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optimization, 1(2):166-190, 1991. [SIOPT:01/0801013].
[34] Pavel Pudlák: Lower bounds for resolution and cutting plane proofs and monotone computations. Journal of Symbolic Logic, 62(3):981-998, September 1997.
[35] G. Stalmark: Short resolution proofs for a sequence of tricky formulas. Acta Informatica, 33(3):277-280, 1996. [ActaInf:lhrhe2glkmgflbu1].
[36] T. Stephen and L. Tunçel: On a representation of the matching polytope via semidefinite liftings. Mathematics of Operations Research, 24(1):1-7, 1999. [ http ]
[37] I. Tourlakis: New lower bounds for vertex cover in the Lovász-Schrijver hierarchy. Manuscript, 2005.
[38] I. Tourlakis: Towards optimal integrality gaps for hypergraph vertex cover in the Lovász-Schrijver hierarchy. In Proceedings of Eighth International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and Ninth International Workshop on Randomization and Computation, pp. 233-244, 2005. [ .ps ]
[39] G.S. Tseitin: On the complexity of derivation in the propositional calculus. In A.O. Slisenko, editor, Studies in Constructive Mathematics and Mathematical Logic, Part II. 1968.

This file has been generated by bibtex2html 1.85.