Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

n this talk we consider linear integer optimization problems in standard form, also referred to as general knapsack problems. In the first part of the talk, I will give a general introduction on how to use dynamic programming to solve knapsack problems in pseudo polynomial time. A key tool for this is to bound the distance from a vertex of a knapsack polyhedron to its nearest feasible lattice point.

In the second part, I will present an optimal upper bound for the vertex distance for knapsack polyhedra with a single linear constraint. For a randomized setting, I will show that the upper bound can be significantly improved on average. This part is joint work with Iskander Aliev and Martin Henk.