Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack

Details Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack

2010-07-08

arxiv.org/abs/1007.1283v1

Computer Science

Computational Complexity

15 pages

Scientific paper

In this paper, we study the integrality gap of the Knapsack linear program in the Sherali- Adams and Lasserre hierarchies. First, we show that an integrality gap of 2 - {\epsilon} persists up to a linear number of rounds of Sherali-Adams, despite the fact that Knapsack admits a fully polynomial time approximation scheme [27,33]. Second, we show that the Lasserre hierarchy closes the gap quickly. Specifically, after t rounds of Lasserre, the integrality gap decreases to t/(t - 1). To the best of our knowledge, this is the first positive result that uses more than a small number of rounds in the Lasserre hierarchy. Our proof uses a decomposition theorem for the Lasserre hierarchy, which may be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-102204