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

Integrality gaps of integer knapsack problems

Aliev, Iskander, Henk, Martin and Oertel, Timm 2017. Integrality gaps of integer knapsack problems. Lecture Notes in Computer Science 10328 , pp. 25-38. 10.1007/978-3-319-59250-3_3

[img]
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: 27 Jan 2019 22:54
URI: http://orca.cf.ac.uk/id/eprint/100933

Citation Data

Cited 2 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