Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

On Distances to Lattice Points in Knapsack Polyhedra -- talk by Iskandier Aliev Event

8 November 2018

Event details

We present 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. The talk is based on a joint work with Martin Henk (TU Berlin) and Timm Oertel (Cardiff University).

Speaker information

Iskandier Aliev,Cardiff University,Dr Iskander Aliev is a Reader at Cardiff School of Mathematics. His research interests are in integer optimisation, discrete computational geometry and algorithmic geometry of numbers. Iskander obtained his PhD in 2001 from the Institute of Mathematics of the Polish Academy of Sciences under supervision of Prof. Andrzej Schinzel. Following completion of his PhD studies he received the Lise-Meitner fellowship from the Austrian Science Fund (FWF) and joined the group of Prof. Peter Gruber at Vienna University of Technology (TU Wien). In 2005, Iskander was offered a postdoctoral fellowship from the University of Edinburgh, where he worked with Prof. Chris Smyth. In 2007 he moved to Cardiff University as a WIMCS (Wales Institute of Mathematical and Computational Sciences) research fellow.

Privacy Settings