Support
Swiss National Science Foundation (SNSF)
Members
Description
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?