Integer optimization in pseudopolynomial time and beyond: For all - there exist statements

Prof. Dr. Robert Weismantel, ETZ Zürich

A classical result of Papadimitriou from 1982 states that integer optimization problems in standard form can be solved in running time max{||b||_\infty, Δ}^{O(m²)} where m denotes the number of equations of the given system, Δ is the largest absolute value of an entry in the system of equations and b denotes the given right hand side vector. This result was improved by Eisenbrand and myself in 2017 to give a running time of {Δ}^{O(m)}. Recently it was shown by Knop, Pilipczuk, Wrochna that this running time is best possible under the exponential time hypothesis. This talk surveys the tools that led to this development.
In a second part we will consider extensions that allow us to tackle. For all - there exist statements. These are associated with a given matrix W and are questions of the form: For every integer vector b in a convex set Q, does there exist an integer vector x such that Wx ≤ b? This is joint work with E. Bach and F. Eisenbrand.