Aliev I, Henk M, Oertel T (2017)
Publication Type: Conference contribution
Publication year: 2017
Publisher: Springer Verlag
Book Volume: 10328 LNCS
Pages Range: 25-38
Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Event location: Waterloo, ON, CAN
ISBN: 9783319592497
DOI: 10.1007/978-3-319-59250-3_3
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.
APA:
Aliev, I., Henk, M., & Oertel, T. (2017). Integrality gaps of integer knapsack problems. In Friedrich Eisenbrand, Jochen Koenemann (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 25-38). Waterloo, ON, CAN: Springer Verlag.
MLA:
Aliev, Iskander, Martin Henk, and Timm Oertel. "Integrality gaps of integer knapsack problems." Proceedings of the 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017, Waterloo, ON, CAN Ed. Friedrich Eisenbrand, Jochen Koenemann, Springer Verlag, 2017. 25-38.
BibTeX: Download