Distances to lattice points in knapsack polyhedra

Aliev I, Henk M, Oertel T (2020)

Publication Type: Journal article

Publication year: 2020

Journal

Mathematical Programming Springer Verlag (Germany)

Book Volume: 182

Pages Range: 175-198

Journal Issue: 1-2

DOI: 10.1007/s10107-019-01392-1

Abstract

We give an optimal upper bound for the ℓ∞-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.

Authors with CRIS profile

Timm Oertel

Additional Organisation(s)

Professur für Mathematische Analyse von Daten (Data Analytics)

Involved external institutions

Technische Universität Berlin DE Germany (DE) Cardiff University GB United Kingdom (GB)

How to cite

APA:

Aliev, I., Henk, M., & Oertel, T. (2020). Distances to lattice points in knapsack polyhedra. Mathematical Programming, 182(1-2), 175-198. https://dx.doi.org/10.1007/s10107-019-01392-1

MLA:

Aliev, Iskander, Martin Henk, and Timm Oertel. "Distances to lattice points in knapsack polyhedra." Mathematical Programming 182.1-2 (2020): 175-198.

BibTeX: Download