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

2010/07/08 by Karlin, Anna R., Mathieu, Claire, Nguyen, C. Thach · 1 citation
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1007.1283

Abstract

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 - ε 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.

Cited by

• Linear Programming Hierarchies Collapse under Symmetry

Related

• An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack
• Integrality Gaps of Integer Knapsack Problems
• The Lasserre Hierarchy in Almost Diagonal Form
• Understanding Set Cover: Sub-exponential Time Approximations and\n Lift-and-Project Methods
• A Knapsack Intersection Hierarchy Applied to All-or-Nothing Flow in Trees