Thursday, September 25, 2003
HP Labs Colloquium: Prof. Bernd Sturmfels, 2003-04 HP
Visiting Research Professor at MSRI. "Gröbner Bases in Integer
Programming." Yosemite 3L, Palo Alto.
Gröbner Bases in Integer Programming
The problem of integer programming is to minimize a linear cost function over the set of non-negative integer solutions to a linear system of equations. This lecture gives an introduction to the use of algebraic methods (Gröbner bases and rational generating functions) in integer programming. Using recent work of Barvinok and Woods, we show that the Gröbner bases of an integer program can be computed in polynomial time when the dimension is fixed. We also discuss computing the integer programming gap and its applications to a problem in statistics.
Host: Gadiel Seroussi
TURMFELS: HEWLETT-PACKARD VISITING
RESEARCH PROFESSOR, 2003-2004
Professor Bernd Sturmfels of the University of California at Berkeley, and a
member at MSRI in the programs on Discrete and Computational Geometry and
Topology of Real Algebraic Varieties, has been appointed as the Hewlett-Packard
Visitng Research Professor for the 2003-2004 academic year. Professor Sturmfels
has been at UCB since 1995, was a fellow of the Sloan foundation 1991-93 and a
David and Lucile Packard Fellow in the period 1992-97. He helped organize the
MSRI programs in Symbolic Computation in Geometry and Analysis in Fall 1998 and
in Commutative Algebra, 2002-2003.
Since 1999, Hewlett-Packard Laboratories have provided funds to support a
Hewlett-Packard Visiting Research Professor at MSRI. The Hewlett-Packard
Visiting Research Professor is selected from applicants by a joint MSRI/HP
Scientific Committee. This position has been filled by researchers at the top of
their fields who come to MSRI to do research and give scientific guidance. The
Hewlett-Packard Visiting Research Professor also collaborates with researchers
at Hewlett-Packard Labs on problems of mutual interest, often involving graduate
students and postdoctoral fellows in these projects. The past holders of this position have been Richard Karp, Hendrik W.
Lenstra, Gabor T. Herman, Sergio Verdu and Sandu Popescu.
Professor Sturmfels will work with researchers at HP on problems related various
areas of interest to the Labs, including coding theory, computational geometry,
and algebraic aspects of statistical modeling.