Leírás
Joint meeting of the BBC + G (Big Budapest Combinatorics + Geometry) seminar and the Combinatorics seminar at Renyi Institute.
Abstract: An integer program is an optimization problem of the form
max {c^T x ： Ax = b, x ∈ℤ_+} where A ∈ ℤ^{m ×n} and b ∈ℤ^m. The complexity of integer programming is a showcase for innovative methods in mathematics and computer science involving, for example, the geometry of numbers as well as recent lower bound techniques, based on assumptions like the exponential-time hypothesis.
In this talk, I will survey some recent developments concerning pseudopolynomial time algorithms for integer programming in the case where the constraint matrix has a small number of rows. Furthermore, I will present an efficient pseudopolynomial time algorithm for general ∀-∃-statements involving few constraints. Based on joint work with Eleonore Bach (EPFL) and Robert Weismantel (ETH) .