Integrality gaps of integer knapsack problems

Aliev, Iskander ORCID: https://orcid.org/0000-0002-2206-9207, Henk, Martin and Oertel, Timm ORCID: https://orcid.org/0000-0001-5720-8978 2017. Integrality gaps of integer knapsack problems. Lecture Notes in Computer Science 10328 , pp. 25-38. 10.1007/978-3-319-59250-3_3

Preview

PDF - Accepted Post-Print Version Download (296kB) | Preview

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.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Publisher:	Springer Verlag
ISSN:	0302-9743
Date of First Compliant Deposit:	27 May 2017
Date of Acceptance:	10 May 2017
Last Modified:	04 Dec 2024 05:30
URI:	https://orca.cardiff.ac.uk/id/eprint/100933

Citation Data

Cited 6 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item