Raymond Hemmecke : Graver and Gr"obner complexity of matrices

Posted by , part of the Algebraic Geometry Seminar.

At

Aug. 27, 2009, 4 p.m.

In

SEO 636

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.