Distances to lattice points in knapsack polyhedra
成果类型：
Article
署名作者：
Aliev, Iskander; Henk, Martin; Oertel, Timm
署名单位：
Cardiff University; Technical University of Berlin
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-019-01392-1
发表日期：
2020
页码：
175-198
关键词：
摘要：
We give an optimal upper bound for the l(infinity)-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.
来源URL：