Paper Info
Title
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].
Year
DOI
Venue
2012
10.1137/100816833
SODA: Symposium on Discrete Algorithms
Keywords
DocType
Volume
tree-like lov,exponential lower bounds,sz-schrijver procedures,maximal rank,lower bound,tree-like refutation,integrality gap,corresponding rank-based integrality gap,size-based lower bound,rank tradeoff,rank tradeoffs,tree-like ls,sz-schrijver procedure,rank-based integrality gap,integrality gaps,size-based integrality gap,small rank,boolean satisfiability,cutting plane
Journal
41
Issue
ISSN
ISBN
1
0097-5397
978-0-89871-698-6
Citations 
PageRank 
References 
11
0.54
27
Authors
2
Name
Order
Citations
PageRank
Toniann Pitassi12282155.18
Nathan Segerlind222311.22