On the Rank of Cutting-Plane Proof Systems

1. Balas, E., Ceria, S., Cornuejols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming 58, 295–324 (1993)

   Article  MathSciNet  Google Scholar 

2. Bockmayr, A., Eisenbrand, F., Hartmann, M., Schulz, A.: On the Chvátal rank of polytopes in the 0/1 cube. Discrete Applied Mathematics 98, 21–27 (1999)

   Article  MATH  MathSciNet  Google Scholar 

3. 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–584 (1995)

   Google Scholar 

4. 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–292 (2009)

   Google Scholar 

5. Chvátal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics 4, 305–337 (1973)

   Article  MATH  MathSciNet  Google Scholar 

6. Chvátal, V., Cook, W., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear algebra and its applications 114, 455–499 (1989)

   Article  MathSciNet  Google Scholar 

7. Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Mathematics of Operations Research 26, 19–30 (2001)

   Article  MATH  MathSciNet  Google Scholar 

8. Cornuéjols, G.: Valid inequalities for mixed integer linear programs. Mathematical Programming 112, 3–44 (2008)

   Article  MATH  MathSciNet  Google Scholar 

9. Cornuejols, G., Li, Y.: Elementary closures for integer programs. Operations Research Letters 28, 1–8 (2001)

   Article  MATH  MathSciNet  Google Scholar 

10. Cornuéjols, G., Li, Y.: A connection between cutting plane theory and the geometry of numbers. Mathematical Programming 93, 123–127 (2002)

    Article  MATH  MathSciNet  Google Scholar 

11. Cornuéjols, G., Li, Y.: On the rank of mixed 0,1 polyhedra. Mathematical Programming 91, 391–397 (2002)

    Article  MATH  MathSciNet  Google Scholar 

12. Dantchev, S.: Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 311–317 (2007)

    Google Scholar 

13. Dash, S.: An exponential lower bound on the length of some classes of branch-and-cut proofs. Mathematics of Operations Research 30, 678–700 (2005)

    Article  MATH  MathSciNet  Google Scholar 

14. Eisenbrand, F., Schulz, A.: Bounds on the Chvátal rank of polytopes in the 0/1-cube. Combinatorica 23, 245–261 (2003)

    Article  MATH  MathSciNet  Google Scholar 

15. Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 702–712 (2007)

    Google Scholar 

16. Goemans, M., Tuncel, L.: When does the positive semidefiniteness constraint help in lifting procedures? Mathematics of Operations Research 26, 796–815 (2001)

    Article  MATH  MathSciNet  Google Scholar 

17. Gomory, R.: Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society 64, 275–278 (1958)

    Article  MATH  MathSciNet  Google Scholar 

18. Gomory, R.: Solving linear programming problems in integers. In: Bellman, R., Hall, M. (eds.) Proceedings of Symposia in Applied Mathematics X, pp. 211–215. American Mathematical Society, Providence (1960)

    Google Scholar 

19. Gomory, R.: An algorithm for integer solutions to linear programs. In: Recent Advances in Mathematical Programming, pp. 269–302. McGraw-Hill, New York (1963)

    Google Scholar 

20. Lasserre, J.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 293–303. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

21. Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization 1, 166–190 (1991)

    Article  MATH  MathSciNet  Google Scholar 

22. 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–302 (2009)

    Google Scholar 

23. Pokutta, S., Schulz, A.: A note on 0/1 polytopes without integral points and with maximal rank (2009) (preprint)

    Google Scholar 

24. Pokutta, S., Schulz, A.: On the connection of the Sherali-Adams closure and border bases (2009) (submitted)

    Google Scholar 

25. Pudlak, P.: On the complexity of propositional calculus. In: Sets and Proofs, Invited Papers from Logic Colloquium ’97, pp. 197–218. Cambridge University Press, Cambridge (1999)

    Google Scholar 

26. 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–602 (2008)

    Google Scholar 

27. Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lovász-Schrijver LP relaxations of vertex cover and max cut. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 302–310 (2007)

    Google Scholar 

28. Sherali, H., Adams, W.: A hierarchy of relaxations between the continuous and convex representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3, 411–430 (1990)

    Article  MATH  MathSciNet  Google Scholar 

Download references