Convexity, geometry of numbers, and the complexity of integer programming


Swiss National Science Foundation (SNSF)


Friedrich Eisenbrand

Linda Farczadi

Christoph Hunkenschröder

Kim-Manuel Klein

Georg Loho

Matthias Schymura


Integer programming is a very important paradigm in optimization, with many applications ranging from pure mathematics, to everyday life and engineering challenges. It is as follows. Given A ∈ Zm*n, b ∈ Zm and c ∈ Zn, solve max{cx : Ax <= b, x ∈ Zn}. Although integer programming is nowadays used as an industry strength tool, the theory of integer programming contains some of the most prominent mysteries in the field of discrete mathematics. Some of these are also the guiding questions of this proposal: Can an integer program be solved in time 2O(n) times a polynomial in the input length? What is the complexity of proof systems establishing the optimality of a solution?

Selected publications