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

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 - e persists up to a linear number of rounds of Sherali-Adams, despite the fact that Knapsack admits a fully polynomial time approximation scheme [24, 30]. 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). This answers the open question in [9]. Also, 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.

• Publication year

  2010

• Venue

  Conference on Integer Programming and Combinatorial Optimization

• Publication date

  2010-07-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-20807-2_24arXiv 1007.1283
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain

  2010cited by this paper
• Optimal Sherali-Adams Gaps from Pairwise Independence

  2009cited by this paper
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

  2009cited by this paper
• Sherali-adams relaxations of the matching polytope

  2009cited by this paper
• CSP gaps and reductions in the lasserre hierarchy

  2009cited by this paper
• MaxMin allocation via degree lower-bounded arborescences

  2009cited by this paper
• Expander flows, geometric embeddings and graph partitioning

  2009cited by this paper
• Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures

  2009cited by this paper
• . 20 24 v 2 [ cs . D S ] 18 N ov 2 00 9 A ( log n ) Ω ( 1 ) integrality gap for the Sparsest Cut SDP

  2009cited by this paper
• SDP Integrality Gaps with Local̀ 1-Embeddability Subhash Khot

  2009cited by this paper
• Integrality gaps for Sherali-Adams relaxations

  2009cited by this paper
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP

  2009cited by this paper
• SDP Integrality Gaps with Local ell_1-Embeddability

  2009cited by this paper
• Approximate formulations for 0-1 knapsack sets

  2008cited by this paper
• Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities

  2008cited by this paper
• Optimal algorithms and inapproximability results for every CSP?

  2008cited by this paper
• Linear Level Lasserre Lower Bounds for Certain k-CSPs

  2008cited by this paper
• Knapsack Problems

  2008cited by this paper
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies

  2008cited by this paper
• Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

  2008cited by this paper
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

  2007cited by this paper
• Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

  2007cited by this paper
• Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations

  2007cited by this paper
• Intrusion-Resilient Secret Sharing

  2007cited by this paper
• Linear programming relaxations of maxcut

  2007cited by this paper
• One-way multiparty communication lower bound for pointer jumping with applications

  2007cited by this paper
• New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy

  2006cited by this paper
• Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l1 Embeddability of Negative Type Metrics

  2006cited by this paper
• Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies

  2006cited by this paper
• Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy

  2005influential reference
• Noise stability of functions with low influences: Invariance and optimality

  2005cited by this paper
• On Lov[a-acute]sz--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP

  2005cited by this paper
• Lift and project relaxations for the matching and related polytopes

  2004cited by this paper
• Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?

  2004influential reference
• Tree-width and the Sherali-Adams operator

  2004cited by this paper
• An O(n log n) procedure for identifying facets of the knapsack polytope

  2003cited by this paper
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming

  2003cited by this paper
• Rank bounds and integrality gaps for cutting planes procedures

  2003cited by this paper
• COMPLEXITY OF SEMIALGEBRAIC PROOFS

  2003cited by this paper
• Proving integrality gaps without knowing the linear program

  2002cited by this paper
• On semidefinite programming relaxations for graph coloring and vertex cover

  2002cited by this paper
• On the power of unique 2-prover 1-round games

  2002influential reference
• On the optimality of the random hyperplane rounding technique for MAX CUT

  2002cited by this paper
• An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs

  2001cited by this paper
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

  2000cited by this paper
• Global Optimization with Polynomials and the Problem of Moments

  2000cited by this paper
• On the 0/1 knapsack polytope

  1997cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995influential reference
• A Hierarchy of Relaxations and Convex Hull Characterizations for Mixed-integer Zero-one Programming Problems

  1994cited by this paper
• A lift-and-project cutting plane algorithm for mixed 0–1 programs

  1993cited by this paper
• The Complexity of Lifted Inequalities for the Knapsack Problem

  1992cited by this paper
• Cones of Matrices and Set-Functions and 0-1 Optimization

  1991cited by this paper
• A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems

  1990cited by this paper
• Valid inequalities for 0-1 knapsacks and mips with generalised upper bound constraints

  1990cited by this paper
• Algorithms and computer implementations

  1990cited by this paper
• Knapsack Problems: Algorithms and Computer Implementations

  1990cited by this paper
• A hierarchy of relaxation between the continuous and convex hull representations

  1990cited by this paper
• Easily Computable Facets of the Knapsack Polytope

  1989cited by this paper
• Computing low-capacity 0–1 knapsack polytopes

  1982cited by this paper
• Facets of the Knapsack Polytope From Minimal Covers

  1978cited by this paper
• Fast approximation algorithms for knapsack problems

  1977cited by this paper
• Facet of regular 0–1 polytopes

  1975cited by this paper
• Facets of the knapsack polytope

  1975cited by this paper
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

  1975cited by this paper
• Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to 1 Embeddability of Negative Type Metrics

  year unknowncited by this paper
• integrality gap for the Sparsest Cut SDP

  year unknowncited by this paper

• Sum-Of-Squares To Approximate Knapsack

  2025cites this paper
• Linear Programming Hierarchies Collapse under Symmetry

  2025cites this paper
• Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization

  2023cites this paper
• Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

  2023cites this paper
• A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies

  2023cites this paper
• A Knapsack Intersection Hierarchy Applied to All-or-Nothing Flow in Trees

  2022cites this paper
• Correlation Clustering with Sherali-Adams

  2022cites this paper
• Superlinear Integrality Gaps for the Minimum Majority Problem

  2021cites this paper
• Approximate extended formulations for multidimensional knapsack and the unsplittable flow problem on trees

  2021cites this paper
• Sum-of-squares hierarchies for binary polynomial optimization

  2020cites this paper
• Breaking symmetries to rescue sum of squares in the case of makespan scheduling

  2020cites this paper
• Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings

  2020cites this paper
• Fair colorful k-center clustering

  2020cites this paper
• Scheduling with Communication Delays via LP Hierarchies and Clustering

  2020influential citation
• Extension Complexity via Lifting LP Hierarchy Lower Bounds

  2020cites this paper
• Copositive certificates of non-negativity for polynomials on semialgebraic sets

  2019cites this paper
• On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

  2019cites this paper
• C C ] 21 M ay 2 01 2 Hypercontractivity , Sum-of-Squares Proofs , and their Applications

  2018cites this paper
• Polynomial-time probabilistic reasoning with partial observations via implicit learning in probability logics

  2018cites this paper
• Breaking symmetries to rescue Sum of Squares: The case of makespan scheduling

  2018cites this paper
• Integrality gaps for colorful matchings

  2018cites this paper
• Integrality Gaps for Bounded Color Matchings

  2018influential citation
• Polynomial Proof Systems, Effective Derivations, and their Applications in the Sum-of-Squares Hierarchy

  2017cites this paper
• Sum-of-squares rank upper bounds for matching problems

  2017cites this paper
• High Degree Sum of Squares Proofs, Bienstock-Zuckerberg Hierarchy and CG Cuts

  2017cites this paper
• An unbounded Sum-of-Squares hierarchy integrality gap for a polynomially solvable problem

  2017cites this paper
• An unbounded Sum-of-Squares hierarchy integrality gap for a polynomially solvable problem

  2017cites this paper
• Strengths and Limitations of Linear Programming Relaxations

  2017cites this paper
• Positive polynomials on unbounded domains

  2017cites this paper
• Lecture 3 : Lasserre Hierarchy-Properties and Applications

  2017cites this paper
• High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts

  2017cites this paper
• Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: $1.8+ε$ approximation for (Unweighted) TAP)

  2016cites this paper
• Limitations of Linear Programming Techniques for Bounded Color Matchings

  2016cites this paper
• Sum-of-squares rank upper bounds for matching problems

  2016cites this paper
• Strong Relaxations for Discrete Optimization Problems 20-27 / 05 / 16 Lecture : Lovász Theta Body . Introduction to hierarchies

  2016cites this paper
• An Introduction to Polynomial and Semi-Algebraic Optimization

  2015cites this paper
• A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem

  2015cites this paper
• Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II

  2015cites this paper
• On the Power of Lasserre SDP Hierarchy

  2015cites this paper
• No Small Linear Program Approximates Vertex Cover within a Factor 2 -- e

  2015cites this paper
• Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP

  2015cites this paper
• On Linear Programming Relaxations for Unsplittable Flow in Trees

  2015cites this paper
• Approximation Algorithms for Path TSP, ATSP, and TAP via Relaxations

  2015influential citation
• Harvest Planning in Apple Orchards Using an Optimization Model

  2015cites this paper
• On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy

  2015cites this paper
• On the Lasserre/Sum-of-Squares Hierarchy with Knapsack Covering Inequalities

  2014cites this paper
• A Comprehensive Analysis of Lift-and-Project Methods for Combinatorial Optimization

  2014cites this paper
• Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch

  2014cites this paper
• On the Integrality Gap of Directed Steiner Tree Problem

  2014influential citation
• Linear Programming Hierarchies Suffice for Directed Steiner Tree

  2014cites this paper
• Lift-and-Project Methods for Set Cover and Knapsack

  2013influential citation
• The Lasserre Hierarchy in Almost Diagonal Form

  2013influential citation
• Rounding sum-of-squares relaxations

  2013cites this paper
• How to Sell Hyperedges: The Hypermatching Assignment Problem

  2013influential citation
• A Comprehensive Analysis of Polyhedral Lift-and-Project Methods

  2013cites this paper
• The Lasserre hierarchy in Approximation algorithms Lecture Notes for the MAPSP 2013 Tutorial Preliminary version

  2013cites this paper
• Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs

  2013cites this paper
• Hypercontractivity, sum-of-squares proofs, and their applications

  2012cites this paper
• Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods

  2012influential citation
• On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems

  2012cites this paper
• Approximability and proof complexity

  2012cites this paper
• Faster SDP Hierarchy Solvers for Local Rounding Algorithms

  2012cites this paper
• Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs

  2012cites this paper
• Notes on the Decomposition Result of Karlin Et Al. [2] for the Hierarchy of Lasserre

  2012influential citation
• Convex Relaxations and Integrality Gaps

  2012influential citation
• Approximation Limits of Linear Programs (Beyond Hierarchies)

  2012cites this paper
• Hypercontractivity, sum-of-squares proofs, and their applications

  2012cites this paper
• A “joint + marginal” heuristic for 0/1 programs

  2011cites this paper
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives

  2011cites this paper
• Directed Steiner Tree and the Lasserre Hierarchy

  2011cites this paper
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

  2011cites this paper
• Graph Partitioning and Semi-definite Programming Hierarchies

  2011cites this paper
• Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy

  2011cites this paper
• Matroid Matching : the Power of Local Search [ Extended Abstract ]

  2010cites this paper
• Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations

  2010cites this paper
• Matroid matching: the power of local search

  2010cites this paper
• Approximating Sparsest Cut in Graphs of Bounded Treewidth

  2010cites this paper
• An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack

  2010cites this paper
• The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs

  2010cites this paper