Computer Science Colloquium
Time+Place : Tuesday 15/03/2011 14:30 room 337-8 Taub  Bld.
Speaker    : Shmuel Onn
Affiliation: IE&M, Technion
Host       : Johann Makowsky
Title      : The Graver Complexity of Integer Programming
Abstract   :
I will overview our recent algorithmic theory which uses Graver bases to
solve linear and nonlinear integer programming problems in variable
dimension in polynomial time. I will demonstrate the power of this theory by
providing polynomial time solutions of (nonlinear) multiway statistical
table problems, multicommodity flows and stochastic integer programming,
show that this theory is universal and provides a new parametrization of all
of integer programming, and indicate a simple approximation hierarchy
suggested by this framework. The talk will draw from my new monograph
(Nonlinear Discrete Optimization, Zurich Lectures in Advanced Mathematics,
European Mathematical Society, September 2010).
Short Biography:
Shmuel Onn is a Professor of Operations Research at IE&M, Technion.
He received his Ph.D. from Cornell University in 1992 and is a frequent
visitor of the Mathematical Research Institutes at Berkeley, Banff,
Oberwolfach, and ETH Zurich. He is a recipient of the 2010 INFORMS Computing
Society Prize, 2009 IBM Faculty Award, 2005 Henry Taub Prize, and 2005 ORSIS
Prize, and is author of the research monograph Nonlinear Discrete
Optimization published by the European Mathematical Society in September
Refreshments served from 14:15 on,
 	Lecture starts at 14:30
Visit our home page-   <>
Thu Feb 24 14:34:55 IST 2011
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>