Integrality gaps of integer knapsack problems
From MaRDI portal
Abstract: We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical" knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.
Recommendations
- Distances to lattice points in knapsack polyhedra
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- On the approximation of an optimal solution to the integer knapsack problem by optimal solutions to the integer knapsack problem with a restriction on the cardinality
- Knapsack problem with objective value gaps
- scientific article; zbMATH DE number 4057285
Cited in
(13)- Testing additive integrality gaps
- On the approximation of an optimal solution to the integer knapsack problem by optimal solutions to the integer knapsack problem with a restriction on the cardinality
- Testing additive integrality gaps
- Note on the knapsack Markov chain.
- Strong IP formulations need large coefficients
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Definition of the narrow intervals for variables in the integer-valued knapsack problem
- The gap function: evaluating integer programming models over multiple right-hand sides
- Distances to lattice points in knapsack polyhedra
- Knapsack problem with objective value gaps
- Integer knapsack problems with profit functions of the same value range
- A note on the integrality gap of the configuration LP for restricted Santa Claus
- Hard Equality Constrained Integer Knapsacks
This page was built for publication: Integrality gaps of integer knapsack problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401142)
