HP Labs Research Colloquium

Thursday, September 25, 2003
2:00p-3:00p
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.

Some References:

http://front.math.ucdavis.edu/math.CO/0211146

http://front.math.ucdavis.edu/math.OC/0301266

http://front.math.ucdavis.edu/math.CO/0307350

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.