Approximate formulations for 0-1 knapsack sets
From MaRDI portal
Publication:943790
DOI10.1016/j.orl.2007.09.003zbMath1152.90535OpenAlexW2065139435MaRDI 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
Related Items (17)
Knapsack polytopes: a survey ⋮ On the mixing set with a knapsack constraint ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ On inequalities with bounded coefficients and pitch for the min knapsack polytope ⋮ Simple extensions of polytopes ⋮ Tightening simple mixed-integer sets with guaranteed bounds ⋮ Some \(0/1\) polytopes need exponential size extended formulations ⋮ A note on the extension complexity of the knapsack polytope ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Extended formulations in combinatorial optimization ⋮ Evolution of new algorithms for the binary knapsack problem ⋮ Extended formulations in combinatorial optimization ⋮ On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ Unnamed Item ⋮ Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations
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
This page was built for publication: Approximate formulations for 0-1 knapsack sets
