BEGIN:VCALENDAR
BEGIN:VEVENT
SUMMARY:ISE 599 SEMINAR
DESCRIPTION:Speaker: Jesus De Loera, UC DavIs
Talk Title: Algebraic Geometric Algorithms in Discrete Optimization
Abstract: It is common knowledge that the understanding of the geometry of convex bodies has helped speed up algorithms in discrete optimization. \n
\n
For example, cutting planes and facet-description of polyhedra have been crucial in the success of branch-and-bound algorithms for mixed integer linear programming. Another example, is how the ellipsoid method can be used to prove polynomiality results in combinatorial optimization. For the future, the importance of algebra and geometry in optimization is even greater since applications now demand non-linearity constraints together with discrete variables.\n
\n
In the past 5 years two beautiful algebraic geometric algorithms on polyhedra have been used to prove unexpected new results on the computation of integer programs with non-linearly objective functions.\n
\n
The first is Barvinok's algorithm for polytopes, the second is Graver's bases method on polyhedral cones. I will describe these two algorithms and explain why we can now prove theorems that were beyond our reach before. I will also describe attempts to turn these two algorithms into practical computation, not just in theoretical results.\n
\n
This is a nice story collecting results contained in several papers joint work with various subsets of the following people: R. Hemmecke, M. Koeppe, S. Onn, U. Rothblum, and R. Weismantel.\n
Host: Professor Dorit Hochbaum
DTSTART:20101004T140000
LOCATION:GER 309
URL;VALUE=URI:
DTEND:20101004T165000
END:VEVENT
END:VCALENDAR