Integrality gaps of integer knapsack problems

DOI10.1007/978-3-319-59250-3_3zbMATH Open1418.90210arXiv1611.03768OpenAlexW2587867261MaRDI QIDQ2401142FDOQ2401142

Authors: Martin Henk, Timm Oertel, Iskander Aliev 

Publication date: 31 August 2017

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.

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

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (13)

• 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
• 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
• Integer knapsack problems with profit functions of the same value range
• Distances to lattice points in knapsack polyhedra
• Knapsack problem with objective value gaps
• 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)