Integrality gaps of integer knapsack problems

Aliev I, Henk M, Oertel T (2017)

Publication Type: Conference contribution

Publication year: 2017

Journal

Lecture Notes in Computer Science Springer Verlag

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

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.

Authors with CRIS profile

Timm Oertel

Additional Organisation(s)

Professur für Mathematische Analyse von Daten (Data Analytics)

Involved external institutions

Cardiff University GB United Kingdom (GB) Technische Universität Berlin DE Germany (DE)

How to cite

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