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

DOI10.1007/978-3-642-20807-2_24zbMath1341.90112arXiv1007.1283OpenAlexW2148012376MaRDI QIDQ3009771

Claire Mathieu, Anna R. Karlin, C. Thach Nguyen

Publication date: 24 June 2011

Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.1283

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (22)

Fair Colorful k-Center Clustering ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Sum-of-squares rank upper bounds for matching problems ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ A ``joint + marginal heuristic for 0/1 programs ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Integrality gaps for colorful matchings ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP ⋮ Approximating (unweighted) tree augmentation via lift-and-project. II ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Convex Relaxations and Integrality Gaps ⋮ Lift-and-project methods for set cover and knapsack ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Sum-of-Squares Rank Upper Bounds for Matching Problems ⋮ High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem ⋮ Fair colorful \(k\)-center clustering

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate formulations for 0-1 knapsack sets
• The complexity of lifted inequalities for the knapsack problem
• On the \(0/1\) knapsack polytope
• An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope.
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Tree-width and the Sherali-Adams operator
• Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints
• Global Optimization with Polynomials and the Problem of Moments
• Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures
• Easily Computable Facets of the Knapsack Polytope
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
• Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
• Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ℓ1 Embeddability of Negative Type Metrics
• Optimal Sherali-Adams Gaps from Pairwise Independence
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Facets of the knapsack polytope
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Facets of the Knapsack Polytope From Minimal Covers
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• SDP Integrality Gaps with Local ell_1-Embeddability
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Integrality gaps for Sherali-Adams relaxations
• CSP gaps and reductions in the lasserre hierarchy
• MaxMin allocation via degree lower-bounded arborescences
• Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack