Algebraic Geometry Seminar
Raymond Hemmecke
TU Darmstadt/University of Magdeburg
Graver and Gr"obner complexity of matrices
Abstract: Graver bases of matrices were originally introduced in 1975 as optimality certificates in integer programming. Although Graver bases are generally huge already for small matrices, one can show that for N-fold IPs there exists a polynomial time algorithm to solve them. This statement heavily relies on a nice structural result on Graver bases of so-called N-fold matrices found by Santos/Sturmfels and generalized by Hosten/Sullivant. This result leads to the notion of Graver complexity, a finite integer number associated to a matrix. In fact, this number gives the degree of the polynomial agorithm to solve the N-fold IP. In practice, it is extremely challenging to compute the Graver complexity of a given matrix. In an analogous manner, one can introduce the notion of Gr"obner complexity of N-fold IPs and show that both numbers agree for unimodular matrices. It is still an open question, whether in this situation Graver bases and universal Gr"obner bases of the N-fold matrices coincide for any N. In this talk we present the polynomial time algorithm to solve N-fold IPs, introduce Graver and Gr"obner complexity of matrices, and state some challenging open problems.
Thursday August 27, 2009 at 4:00 PM in SEO 636