Paper Info
Title
Integrality gaps of linear and semi-definite programming relaxations for Knapsack
Abstract
Recent years have seen an explosion of interest in lift and project methods, such as those proposed by Lov asz and Schrijver (40), Sherali and Adams (48), Balas, Ceria and Cornuejols (6), Lasserre (36, 37) and others. These methods are systematic procedures for constructing a sequence of increasingly tight mathematical programming relaxations for 0-1 optimization problems. One major line of research in this area has focused on understanding the strengths and limitations of these procedures. Of particular interest to our community is the question of how the integrality gaps for interesting combinatorial optimization problems evolve through a series of rounds of one of these procedures. On the one hand, if the integrality gap of successive relaxations drops suciently fast, there is the potential for an improved approximation algorithm. On the other hand, if the integrality gap for a problem persists, this can be viewed as a lower bound in a certain restricted model of computation. In this paper, we study the integrality gap in these hierarchies for the knapsack problem. We have two main results. First, we show that an integrality gap of 2 persists up to a linear number of rounds of Sherali-Adams. This is interesting, since it is well known that knapsack has a fully polynomial time approximation scheme (30, 39). Second, we show that Lasserre's hierarchy closes the gap quickly. Specically, after t2 rounds of Lasserre, the integrality gap decreases to t=(t 1).
Year
DOI
Venue
2011
10.1007/978-3-642-20807-2_24
integer programming and combinatorial optimization
Keywords
DocType
Volume
integrality gap decrease,integrality gap,semi-definite programming relaxation,lasserre hierarchy,polynomial time approximation scheme,knapsack linear program,independent interest,open question,decomposition theorem,small number,linear number
Conference
abs/1007.1283
ISSN
Citations 
PageRank 
0302-9743
25
1.03
References 
Authors
51
3
Name
Order
Citations
PageRank
Anna R. Karlin14429646.72
Claire Mathieu245225.78
C. Thach Nguyen31148.69