Approximate formulations for 0-1 knapsack sets
From MaRDI portal
Publication:943790
DOI10.1016/j.orl.2007.09.003zbMath1152.90535MaRDI QIDQ943790
Publication date: 10 September 2008
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2007.09.003
90C10: Integer programming
Related Items
Unnamed Item, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Extended formulations in combinatorial optimization, Extended formulations in combinatorial optimization, On the mixing set with a knapsack constraint, Tightening simple mixed-integer sets with guaranteed bounds, Simple extensions of polytopes, On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space, Evolution of new algorithms for the binary knapsack problem, Some \(0/1\) polytopes need exponential size extended formulations, A note on the extension complexity of the knapsack polytope, Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Approximation Limits of Linear Programs (Beyond Hierarchies)
Cites Work
- Unnamed Item
- Unnamed Item
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Tree-width and the Sherali-Adams operator
- Approximate extended formulations
- Approximate fixed-rank closures of covering problems
- On the Matrix-Cut Rank of Polyhedra
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Subset Algebra Lift Operators for 0-1 Integer Programming
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
