Approximate formulations for 0-1 knapsack sets
From MaRDI portal
Recommendations
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- A note on the extension complexity of the knapsack polytope
- scientific article; zbMATH DE number 7122316
- Polynomial size IP formulations of knapsack may require exponentially large coefficients
- Approximation for knapsack problems with multiple constraints
Cites work
- scientific article; zbMATH DE number 3545380 (Why is no real title available?)
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- 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
- Approximate extended formulations
- Approximate fixed-rank closures of covering problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- On the matrix-cut rank of polyhedra.
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Tree-width and the Sherali-Adams operator
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
Cited in
(18)- On inequalities with bounded coefficients and pitch for the min knapsack polytope
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- A note on the extension complexity of the knapsack polytope
- Evolution of new algorithms for the binary knapsack problem
- Knapsack polytopes: a survey
- Extended formulations in combinatorial optimization
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- On the mixing set with a knapsack constraint
- Tightening simple mixed-integer sets with guaranteed bounds
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Extended formulations in combinatorial optimization
- Small extended formulation for knapsack cover inequalities from monotone circuits
- scientific article; zbMATH DE number 7122316 (Why is no real title available?)
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- Polynomial size IP formulations of knapsack may require exponentially large coefficients
- Some \(0/1\) polytopes need exponential size extended formulations
- Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations
- Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes
This page was built for publication: Approximate formulations for 0-1 knapsack sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q943790)
