Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures

ABSTRACT

The matrix cuts of Lovász and Schrijver are methods for tightening linear relaxations of zero-one programs by the addition of new linear inequalities. We address the question of how many new inequalities are necessary to approximate certain combinatorial problems, and to solve certain instances of Boolean satisfiability.

Our first result is a size/rank tradeoff for tree-like Lovász-Schrijver refutations, showing that any refutation that has small size also has small rank. This allows us to immediately derive exponential size lower bounds for tree-like refutations of many unsatisfiable systems of inequalities where prior to our work, only strong rank bounds were known.

Unfortunately, we show that this tradeoff does not hold more generally for derivations of arbitrary inequalities. We give a very simple example showing that derivations can be very small but nonetheless require maximal rank. This rules out a generic argument for obtaining a size-based integrality gap from the corresponding rank-based integrality gap. Our second contribution is to show that a modified argument can often be used to prove size-based integrality gaps from rank-based integrality gaps. We apply this method to prove size-based integrality gaps for several prominant examples where prior to our work, only rank-based integrality gaps were known.

Our third contribution is to prove new separation results. Using our machinery for converting rank-based lower bounds and integrality gaps into size-based lower bounds, we show that tree-like LS₊ cannot polynomially simulate tree-like Cutting Planes, and that tree-like LS⁺ cannot polynomially simulate resolution.

We conclude by examining size/rank tradeoffs beyond the LS systems. We show that for Shirali-Adams and Lasserre systems, size/rank tradeoffs continue to hold, even in the general (non-tree) case.

A full version of this paper is available at the Electronic Colloquium on Computational Complexity [23].

REFERENCES

• 1: Michael Alekhnovich, Lower bounds for k-DNF resolution on random 3-CNFs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060628]
• 2: Mikhail Alekhnovich , Sanjeev Arora , Iannis Tourlakis, Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060634]
• 3: Michael Alekhnovich , Edward A. Hirsch , Dmitry Itsykson, Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas, Journal of Automated Reasoning, v.35 n.1-3, p.51-72, October 2005 [doi>10.1007/s10817-005-9006-x]
• 4: M. Alekhnovich , A. Razborov, Lower Bounds for Polynomial Calculus: Non-Binomial Case, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.190, October 14-17, 2001
• 5: S. Arora, B. Bollobas, L. Lovasz, and I. Tourlakis. Proving integrality gaps without knowing the linear program. Theory of Computing, 2(2):19--51, 2006.
• 6: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 7: Per Austrin, Towards Sharp Inapproximability For Any 2-CSP, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.307-317, October 21-23, 2007 [doi>10.1109/FOCS.2007.73]
• 8: J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen, and T. Pitassi. Rank bounds and integrality gaps for cutting planes procedures. Theory of Computing, 2:65--90, 2006.
• 9: Sam Buss , Dima Grigoriev , Russell Impagliazzo , Toniann Pitassi, Linear gaps between degrees for the polynomial calculus modulo distinct primes, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.547-556, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301399]
• 10: M. Charikar, K. Makarychev, and Y. Makarychev. Integrality gaps for sherali-adams relaxations, 2007.
• 11: Matthew Clegg , Jeffery Edmonds , Russell Impagliazzo, Using the Groebner basis algorithm to find proofs of unsatisfiability, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.174-183, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237860]
• 12: 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.
• 13: Wenceslas Fernandez de la Vega , Claire Kenyon-Mathieu, Linear programming relaxations of maxcut, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.53-61, January 07-09, 2007, New Orleans, Louisiana
• 14: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 15: Dima Grigoriev, Linear lower bound on degrees of positivstellensatz calculus proofs for the parity, Theoretical Computer Science, v.259 n.1-2, p.613-622, May 28, 2001 [doi>10.1016/S0304-3975(00)00157-2]
• 16: D. Grigoriev, E. Hirsch, and D. Pasechnik. Complexity of semialgebraic proofs. Moscow Mathematical Journal, 2:647--679, 2002.
• 17: Dima Grigoriev , Edward A. Hirsch, Algebraic proof systems over formulas, Theoretical Computer Science, v.303 n.1, p.83-102, 28 June 2003 [doi>10.1016/S0304-3975(02)00446-2]
• 18: D. Grigoriev and N. Vorobjov. Complexity of null- and positivestellensatz proofs. Annals of Pure and Applied Logic, 113:153--160, 2001.
• 19: A. Kojevnikov and D. Itsykson. Lower bounds of statis lovasz-schrijver calculus proofs for tseitin tautologies. In ICALP, pages 323--334, 2006.
• 20: G. Konstantinos, A. Magen, T. Pitassi, and I. Tourlakis. Optimal integrality gaps for lovaszschrijver relaxations of vertex cover. In ECCC, 2006.
• 21: L. Lovász. On the Shannon capacity of a graph. IEEE Transactions on Information Theory, 25:1--7, 1979.
• 22: L. Lovasz and A. Schrijver. Cones of matrices and set-functions and 0--1 optimization. SIAM J. Optimization, 1(2):166--190, 1991.
• 23: T. Pitassi and N. Segerlind. Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures. Electronic Colloquium on Computational Complexity, Technical Report TR07-107. Web address: http://eccc.hpi-web.de
• 24: Prasad Raghavendra, Optimal algorithms and inapproximability results for every CSP?, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374414]
• 25: Grant Schoenebeck , Luca Trevisan , Madhur Tulsiani, A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.205-216, June 13-March 16, 2007 [doi>10.1109/CCC.2007.2]
• 26: G. Schoenebeck, L. Trevisan, and M. Tulsiani. Tight integrality gaps for lovasz-schrijver lp relaxations of vertex cover and max cut. In ECCC, 2006.
• 27: Iannis Tourlakis, New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy, Proceedings of the 21st Annual IEEE Conference on Computational Complexity, p.170-182, July 16-20, 2006 [doi>10.1109/CCC.2006.28]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory