Thursday, September 25, 2003
2:00p3:00p
HP Labs Colloquium: Prof. Bernd Sturmfels, 200304 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 nonnegative 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: HEWLETTPACKARD VISITING
RESEARCH PROFESSOR, 20032004
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 HewlettPackard
Visitng Research Professor for the 20032004 academic year. Professor Sturmfels
has been at UCB since 1995, was a fellow of the Sloan foundation 199193 and a
David and Lucile Packard Fellow in the period 199297. He helped organize the
MSRI programs in Symbolic Computation in Geometry and Analysis in Fall 1998 and
in Commutative Algebra, 20022003.
Since 1999, HewlettPackard Laboratories have provided funds to support a
HewlettPackard Visiting Research Professor at MSRI. The HewlettPackard
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
HewlettPackard Visiting Research Professor also collaborates with researchers
at HewlettPackard 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.
