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

Distances to lattice points in knapsack polyhedra

Aliev, Iskander, Henk, Martin and Oertel, Timm 2020. Distances to lattice points in knapsack polyhedra. Mathematical Programming 182 10.1007/s10107-019-01392-1

PDF - Published Version
Available under License Creative Commons Attribution.

Download (346kB) | Preview


We give an optimal upper bound for the maximum norm distance from a vertex of a knapsack polyhedron to its nearest feasible lattice point. In a randomised setting, we show that the upper bound can be significantly improved on average. As a corollary, we obtain an optimal upper bound for the additive integrality gap of integer knapsack problems and show that the integrality gap of a 'typical' knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario. We also prove that, in a generic case, the integer programming gap admits a natural optimal lower bound

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Publisher: Springer Verlag
ISSN: 0025-5610
Related URLs:
Date of First Compliant Deposit: 2 April 2019
Date of Acceptance: 11 March 2019
Last Modified: 16 Nov 2020 16:00

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics