Integrality gaps of linear and semi-definite programming relaxations for knapsack
From MaRDI portal
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 - {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.
Recommendations
Cites work
- A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope.
- Approximate formulations for 0-1 knapsack sets
- Cones of Matrices and Set-Functions and 0–1 Optimization
- CSP gaps and reductions in the lasserre hierarchy
- Easily Computable Facets of the Knapsack Polytope
- Expander flows, geometric embeddings and graph partitioning
- Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures
- Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
- Facets of the knapsack polytope
- Facets of the Knapsack Polytope From Minimal Covers
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Global optimization with polynomials and the problem of moments
- scientific article; zbMATH DE number 5485464 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 3606249 (Why is no real title available?)
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- scientific article; zbMATH DE number 2119717 (Why is no real title available?)
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Integrality gaps for Sherali-Adams relaxations
- Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
- Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy
- Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ℓ1 Embeddability of Negative Type Metrics
- Linear programming relaxations of \textsc{maxcut}
- MaxMin allocation via degree lower-bounded arborescences
- On the \(0/1\) knapsack polytope
- Optimal Sherali-Adams Gaps from Pairwise Independence
- Proving integrality gaps without knowing the linear program
- Rank bounds and integrality gaps for cutting planes procedures
- SDP Integrality Gaps with Local ell₁-Embeddability
- The complexity of lifted inequalities for the knapsack problem
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
- Tree-width and the Sherali-Adams operator
- Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints
- Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities
Cited in
(27)- Sum-of-squares rank upper bounds for matching problems
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
- Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
- Approximating (unweighted) tree augmentation via lift-and-project. II
- Lift-and-project methods for set cover and knapsack
- A ``joint + marginal heuristic for 0/1 programs
- Fair colorful \(k\)-center clustering
- Integrality gaps of integer knapsack problems
- Integrality gaps for colorful matchings
- A comprehensive analysis of polyhedral lift-and-project methods
- Convex relaxations and integrality gaps
- Sum-of-squares rank upper bounds for matching problems
- Lift-and-project methods for set cover and knapsack
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- A Lasserre lower bound for the min-sum single machine scheduling problem
- Superlinear Integrality Gaps for the Minimum Majority Problem
- Fair colorful k-center clustering
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
- Sum-of-squares hierarchies for binary polynomial optimization
- On the integrality gap of binary integer programs with Gaussian data
- Sum-of-squares hierarchies for binary polynomial optimization
- A knapsack intersection hierarchy
- Branch-and-bound versus lift-and-project relaxations in combinatorial optimization
- Linear programming hierarchies collapse under symmetry
This page was built for publication: Integrality gaps of linear and semi-definite programming relaxations for knapsack
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3009771)
