Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

[thumbnail of IntegralityGapsIPCO2017-revision.pdf]
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: 06 Nov 2023 18:47
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 Edit Item

Downloads

Downloads per month over past year

View more statistics