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 |
Official URL: http://dx.doi.org/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.
| Item Type: | Article |
|---|---|
| Date Type: | Publication |
| Status: | Published |
| Schools: | 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 |
Dimensions
Dimensions